- Title
- Incremental network design with shortest paths
- Creator
- Baxter, Matthew; Elgindy, Tarek; Ernst, Andreas T.; Kalinowski, Thomas; Savelsbergh, Martin W. P.
- Relation
- European Journal of Operational Research Vol. 238, Issue 3, p. 675-684
- Publisher Link
- http://dx.doi.org/10.1016/j.ejor.2014.04.018
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2014
- Description
- 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.
- Subject
- network design; multi-period; heuristic; approximation algorithm; integer programming
- Identifier
- http://hdl.handle.net/1959.13/1296356
- Identifier
- uon:19239
- Identifier
- ISSN:0377-2217
- Language
- eng
- Reviewed
- Hits: 2586
- Visitors: 2781
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|