Incremental network design with shortest paths

Matthew Baxter, Tarek Elgindy, Andreas Tilman Ernst, Thomas Kalinowski, Martin WP Savelsbergh

Research output: Contribution to journalArticleResearchpeer-review

34 Citations (Scopus)


We introduce a class of incremental network design problems focused on investigating the optimal choice and timing of network expansions. We concentrate on an incremental network design problem with shortest paths. We investigate structural properties of optimal solutions, show that the simplest variant is NP-hard, analyze the worst-case performance of natural greedy heuristics, derive a 4-approximation algorithm, and conduct a small computational study.
Original languageEnglish
Pages (from-to)675-684
Number of pages10
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 Nov 2014
Externally publishedYes

Cite this