• AMSI ACCESS GRID SEMINAR
  • Speaker: Prof Martin Savelsbergh, School of Mathematical and Physical Sciences, The University of Newcastle
  • Title: Incremental Network Design
  • Location: Room V206, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Access Grid Venue: UNewcastle [ENQUIRIES]
  • Time and Date: 2:30 pm, Tue, 28th May 2013
  • Abstract:

    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 examine three variants: incremental network design with shortest paths, incremental network design with maximum flows, and incremental design with minimum spanning trees. We investigate their computational complexity, we analyse the performance of natural heuristics, we derive approximation algorithms and we study integer program formulations.


  • [Permanent link]