TY - CONF
T1 - Efficient algorithms for location and sizing problems in network design
T2 - IEEE Global Telecommunications Conference, 2001. GLOBECOM '01
Y1 - 2001
A1 - Kumaran,K.
A1 - Srinivasan, Aravind
A1 - Qiong Wang
A1 - Lanning,S.
A1 - Ramakrishnan,K. G
KW - Algorithm design and analysis
KW - Broadband communication
KW - broadband communication networks
KW - broadband networks
KW - capacity modularity
KW - Communication networks
KW - computer network reliability
KW - distributed network elements
KW - Economies of scale
KW - greedy randomized adaptive search
KW - homing
KW - integer programming
KW - Intelligent networks
KW - Internet telephony
KW - large-scale location problems
KW - Large-scale systems
KW - Linear programming
KW - mixed-integer programs
KW - near-optimal solutions
KW - network design
KW - Optical switches
KW - randomised algorithms
KW - reliability
KW - search problems
KW - sizing
KW - Technological innovation
KW - telecommunication network planning
KW - Web caching
AB - 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
JA - IEEE Global Telecommunications Conference, 2001. GLOBECOM '01
PB - IEEE
VL - 4
SN - 0-7803-7206-9
M3 - 10.1109/GLOCOM.2001.966243
ER -