Incremental network design with shortest paths

Author(s)
Baxter, Matthew
Elgindy, Tarek
Ernst, Andreas T
Kalinowski, Thomas
Savelsbergh, Martin W P
Publication Date
2014-11-01
Abstract
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.
Citation
European Journal of Operational Research, 238(3), p. 675-684
ISSN
1872-6860
0377-2217
Link
https://hdl.handle.net/1959.11/26796
Publisher
Elsevier BV
Title
Incremental network design with shortest paths
Type of document
Journal Article
Entity Type
Publication

Files:

NameSizeformatDescriptionLink