Incremental network design with shortest paths

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.

MoreLess

Year of publication:	2014
Authors:	Baxter, Matthew ; Elgindy, Tarek ; Ernst, Andreas T. ; Kalinowski, Thomas ; Savelsbergh, Martin W.P.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 238.2014, 3, p. 675-684
Publisher:	Elsevier
Subject:	Network design \| Multi-period \| Heuristic \| Approximation algorithm \| Integer programming

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010871257