Incremental network design with shortest paths

•We study the optimal choice and timing of network expansions.•We introduce a new class of incremental network design problems.•We develop a 4-approximation algorithm for incremental network design with shortest paths.•Analysis shows that coordinating timing of expansions increases the complexity of...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2014-11, Vol.238 (3), p.675-684
Main Authors: Baxter, Matthew, Elgindy, Tarek, Ernst, Andreas T., Kalinowski, Thomas, Savelsbergh, Martin W.P.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithm
Heuristic
Incremental networks
Integer programming
Job shops
Mathematical models
Mathematical problems
Multi-period
Network design
Networks
Operational research
Optimization
Shortest path algorithms
Shortest-path problems
Studies
Time measurements
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We study the optimal choice and timing of network expansions.•We introduce a new class of incremental network design problems.•We develop a 4-approximation algorithm for incremental network design with shortest paths.•Analysis shows that coordinating timing of expansions increases the complexity of network design. 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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2014.04.018