TY - GEN
T1 - Buy-at-bulk network design with protection
AU - Antonakopoulos, Spyridon
AU - Chekuri, Chandra Sekhar
AU - Shepherd, Bruce
AU - Zhang, Lisa
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=46749095566&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=46749095566&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2007.4389532
DO - 10.1109/FOCS.2007.4389532
M3 - Conference contribution
AN - SCOPUS:46749095566
SN - 0769530109
SN - 9780769530109
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 634
EP - 644
BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Y2 - 20 October 2007 through 23 October 2007
ER -