Title: Approximation algorithm for optimal location of concentrators and design of Capacitated Survivable Backbone Networks
Authors: Arun Jotshi, Sarat Puthenpura, Wenjie Zhao
Addresses: AT&T Shannon Labs, 180 Park Avenue, Florham Park, NJ 07932, USA. ' AT&T Shannon Labs, 180 Park Avenue, Florham Park, NJ 07932, USA. ' AT&T Shannon Labs, 180 Park Avenue, Florham Park, NJ 07932, USA
Abstract: We focus on the problem of selecting concentrator locations to minimise the access network costs. This falls under the general class of Uncapacitated Facility Location (UFL) problem. We present an approximation algorithm along with some computational results. We also study the problem of designing a Capacitated Survivable Backbone Network (CSBN) with the property that there is at least one route present between all the communicating node pairs in the case of a single link failure. Mathematical formulation to efficiently solve the survivable backbone network design problem is presented. The methodologies developed are applied to a real world setting obtaining optimal or near-optimal results.
Keywords: facility location; access networks; survivable backbone networks; capacitated backbone networks; k-connected networks; concentrator locations; network costs; link failure; network design.
International Journal of Mathematics in Operational Research, 2011 Vol.3 No.1, pp.22 - 43
Available online: 03 Dec 2010 *Full-text access for editors Access for subscribers Purchase this article Comment on this article