Efficient algorithms for location and sizing problems in network design

TitleEfficient algorithms for location and sizing problems in network design
Publication TypeConference Papers
Year of Publication2001
AuthorsKumaran K, Srinivasan A, Wang Q, Lanning S, Ramakrishnan KG
Conference NameIEEE Global Telecommunications Conference, 2001. GLOBECOM '01
Date Published2001///
ISBN Number0-7803-7206-9
KeywordsAlgorithm design and analysis, Broadband communication, broadband communication networks, broadband networks, capacity modularity, Communication networks, computer network reliability, distributed network elements, Economies of scale, greedy randomized adaptive search, homing, integer programming, Intelligent networks, Internet telephony, large-scale location problems, Large-scale systems, Linear programming, mixed-integer programs, near-optimal solutions, network design, Optical switches, randomised algorithms, reliability, search problems, sizing, Technological innovation, telecommunication network planning, Web caching

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