Buy-at-bulk network design with protection

Spyridon Antonakopoulos, Chandra Chekuri, Bruce Shepherd, Lisa Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against a single edge or node failure in the network. In practice, the most popular model used in high-speed telecommunication networks for protection against failures is the so-called 1+1 model. In this model, two-edge or nodedisjoint paths are provisioned for each demand pair. We obtain the first nontrivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case and a polylogarithmic factor approximation for the multicommodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

Original languageEnglish (US)
Pages (from-to)71-87
Number of pages17
JournalMathematics of Operations Research
Volume36
Issue number1
DOIs
StatePublished - Feb 1 2011

Keywords

  • 1+1 Protection
  • Approximation algorithms
  • Buy-at-bulk
  • Network design

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Buy-at-bulk network design with protection'. Together they form a unique fingerprint.

Cite this