Efficient algorithms for location and sizing problems in network design

Krishnan Kumaran, Aravind Srinivasan, Qiong Wang, Steven Lanning, K. G. Ramakrishnan

Research output: Contribution to conferencePaperpeer-review


Large-scale location, sizing and homing problems of distributed network elements, have received much attention recently due to the massive deployment of broadband communication networks for services like Internet telephony and Web caching. Key considerations in designing these networks include modularity of capacity, economies of scale in cost, and reliability. We formulate a general class of such network design problems as Mixed-Integer Programs. These problems are computationally intractable in general; under various asymptotic conditions, we show how to compute near-optimal solutions. To deal with arbitrary instances, we develop new algorithms based on linear programming, as well as greedy randomized adaptive search. These algorithms achieved near-optimal solutions with reasonable computation time for our experiments.

Original languageEnglish (US)
Number of pages5
StatePublished - 2001
Externally publishedYes
EventIEEE Global Telecommunicatins Conference GLOBECOM'01 - San Antonio, TX, United States
Duration: Nov 25 2001Nov 29 2001


OtherIEEE Global Telecommunicatins Conference GLOBECOM'01
Country/TerritoryUnited States
CitySan Antonio, TX

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Global and Planetary Change


Dive into the research topics of 'Efficient algorithms for location and sizing problems in network design'. Together they form a unique fingerprint.

Cite this