Buy‐at‐Bulk Network Design with Protection

Buy‐at‐Bulk Network Design with Protection

0.00 Avg rating0 Votes
Article ID: iaor20113640
Volume: 36
Issue: 1
Start Page Number: 71
End Page Number: 87
Publication Date: Feb 2011
Journal: Mathematics of Operations Research
Authors: , , ,
Keywords: design, quality & reliability
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 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.

Reviews

Required fields are marked *. Your email address will not be published.