Buy-at-bulk network design with protection

Spyridon Antonakopoulos, Chandra Sekhar Chekuri, Bruce Shepherd, Lisa Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures 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 node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial 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 an O (log 3 n) approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages634-644
Number of pages11
DOIs
StatePublished - Dec 1 2007
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

ASJC Scopus subject areas

  • Engineering(all)

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

Cite this