Incremental network design with shortest paths

Title
Incremental network design with shortest paths
Publication Date
2014-11-01
Author(s)
Baxter, Matthew
Elgindy, Tarek
Ernst, Andreas T
Kalinowski, Thomas
( author )
OrcID: https://orcid.org/0000-0002-8444-6848
Email: tkalinow@une.edu.au
UNE Id une-id:tkalinow
Savelsbergh, Martin W P
Type of document
Journal Article
Language
en
Entity Type
Publication
Publisher
Elsevier BV
Place of publication
Netherlands
DOI
10.1016/j.ejor.2014.04.018
UNE publication id
une:1959.11/26796
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.
Link
link
Citation
European Journal of Operational Research, 238(3), p. 675-684
ISSN
1872-6860
0377-2217
Start page
675
End page
684

Files:

NameSizeformatDescriptionLink