Buy-at-Bulk Network Design with Protection

• 成果类型: Article
• 署名作者: Antonakopoulos, Spyridon; Chekuri, Chandra; Shepherd, Bruce; Zhang, Lisa
• 署名单位: Alcatel-Lucent; AT&T; University of Illinois System; University of Illinois Urbana-Champaign; McGill University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0484
• 发表日期: 2011
• 页码: 71-87
• 关键词: approximation algorithms

摘要

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 node-disjoint 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.