Efficient Algorithms for Location and Sizing Problems in Communications Network Design

Large-scale location, sizing and homing problems of distributed network elements have received much attention recently due to the massive deployment of emerging broadband communication networks for services like Internet telephony and Web caching. Important considerations in designing these networks include modularity of capacity, economies of scale in cost, and reliability through redundant configuration. We formulate a general class of these network design problems as Mixed-Integer Linear Programs. These problems are computationally intractable in general, and no good approximation algorithms are known. Under various asymptotic conditions, such as large user demands, we show how to compute near-optimal solutions. Furthermore, to deal with arbitrary instances, we develop new algorithms based on linear programming relaxation and rounding, as well as greedy randomized adaptive search (GRASP). These algorithms achieved near- optimal solutions with reasonable computation time for our numerical experiments, thus demonstrating their practical utility.