Incremental network design with shortest paths

Matthew Baxter; Tarek Elgindy; Andreas T Ernst; Thomas Kalinowski; Martin W P Savelsbergh

doi:10.1016/j.ejor.2014.04.018

Incremental network design with shortest paths

Matthew Baxter, Tarek Elgindy, Andreas T Ernst, Thomas Kalinowski, Martin W P Savelsbergh

School of Science & Technology

Research output: Contribution to journal › Article › peer-review

47 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	675-684
Journal	European Journal of Operational Research
Volume	238
Issue number	3
Early online date	24 Apr 2014
DOIs	https://doi.org/10.1016/j.ejor.2014.04.018
Publication status	Published - 1 Nov 2014

Access to Document

10.1016/j.ejor.2014.04.018

https://hdl.handle.net/1959.11/26796

Handle.net

Persistent link

Cite this

@article{04d6f12b96a646c09e3137ac172699fd,

title = "Incremental network design with shortest paths",

abstract = "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.",

author = "Matthew Baxter and Tarek Elgindy and Ernst, \{Andreas T\} and Thomas Kalinowski and Savelsbergh, \{Martin W P\}",

year = "2014",

month = nov,

day = "1",

doi = "10.1016/j.ejor.2014.04.018",

language = "English",

volume = "238",

pages = "675--684",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier BV",

number = "3",

}

TY - JOUR

T1 - Incremental network design with shortest paths

AU - Baxter, Matthew

AU - Elgindy, Tarek

AU - Ernst, Andreas T

AU - Kalinowski, Thomas

AU - Savelsbergh, Martin W P

PY - 2014/11/1

Y1 - 2014/11/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84902103615

U2 - 10.1016/j.ejor.2014.04.018

DO - 10.1016/j.ejor.2014.04.018

M3 - Article

SN - 0377-2217

VL - 238

SP - 675

EP - 684

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Incremental network design with shortest paths

Abstract

Access to Document

Handle.net

Fingerprint

Cite this