• Speaker: Prof Martin Savelsbergh, School of Mathematical and Physical Sciences, The University of Newcastle
  • Title: Incremental Network Design with Shortest Paths
  • Location: Room V206, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Access Grid Venue: UNewcastle [ENQUIRIES]
  • Time and Date: 6:00 pm, Wed, 21st Mar 2012
  • 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 focus on the simplest variant: incremental network design with shortest paths, and show that even its simplest variant is NP-hard. We investigate structural properties of optimal solutions, we analyze the worst-case performance of natural greedy heuristics, we derive a 4-approximation algorithm, and we present an integer program formulation and conduct a small computational study.

    Joint work with

    Matthew Baxter
    Tarek Elgindy
    Andreas Ernst
    CSIRO Mathematics Informatics and Statistics

    Thomas Kalinowski
    Institute for Mathematics
    University of Rostock, Germany

  • [Permanent link]