Incremental network design problems
Professor Martin Savelsbergh, University of Newcastle
21st Sep 2012 11:00 am - Room 498 Merewether Building H04
Network infrastructures are a common phenomenon. Network upgrades and expansions typically occur over time due to budget constraints.
We introduce a class of incremental network design problems that allow investigation of many of the key issues related to the choice and timing of infrastructure expansions and their impact on the costs of the activities performed on that infrastructure. We focus on two variants: incremental network design with shortest paths and incremental network design with maximum flows. We consider the complexity of the problem, we analyze the performance of natural heuristics, we derive approximation algorithms, and we study integer program formulations.