|
|||||
|
|
Incremental network design with shortest paths |
|
| Authors: | Matthew Baxter Tarek Elgindy Andreas T. Ernst Thomas Kalinowski Martin W.P. Savelsbergh |
| Affiliation: | 1. CSIRO Mathematics Informatics and Statistics, CSIRO, Australia;2. University of Newcastle, Australia |
| 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. |
| Keywords: | Network design Multi-period Heuristic Approximation algorithm Integer programming |
| 本文献已被 ScienceDirect 等数据库收录！ | |