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.

DOI: 10.1504/IJMOR.2011.037311

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