Approximation Algorithms for Access Network Design

We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale. A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. WSe formulate the problem as an integer programs. We first us a primal-dual approach to obtain a solution whose cost is within O(K sup 2) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K). Both bounds are obtained under weak assumptions on the trunk costs. Our primal-dual algorithm is motivated by the work of Jain and Varirani on facility location. Our rounding algorithm improves upon the access network algorithm presented in [1] and is motivated by the facility location algorithm of Shmoys, Tardos and Aardal [13].