Efficient algorithms for location and sizing problems in network design
| Title | Efficient algorithms for location and sizing problems in network design |
| Publication Type | Conference Papers |
| Year of Publication | 2001 |
| Authors | Kumaran K, Srinivasan A, Wang Q, Lanning S, Ramakrishnan KG |
| Conference Name | IEEE Global Telecommunications Conference, 2001. GLOBECOM '01 |
| Date Published | 2001/// |
| Publisher | IEEE |
| ISBN Number | 0-7803-7206-9 |
| Keywords | Algorithm 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 |
| Abstract | 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 |
| DOI | 10.1109/GLOCOM.2001.966243 |