Find us on Facebook Find us on LinkedIn Follow us on Twitter Subscribe to our YouTube channel

Business Analytics

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.