This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Bollapragada, R. Articles by Rao, U. S. Search for Related Content

Budget-Constrained, Capacitated Hub Location to Maximize Expected Demand Coverage in Fixed-Wireless Telecommunication Networks

College of Business, San Francisco State University, 1600 Holloway Avenue, San Francisco, California 94132, USA, and Bell Laboratories, Lucent Technologies, Holmdel, New Jersey 07733, USA
Krannert School of Management, Purdue University, West Lafayette, Indiana 47907, USA
College of Business, University of Cincinnati, P.O. Box 210130, Cincinnati, Ohio 45221, USA
rbollapragada{at}yahoo.com
li14{at}mgmt.purdue.edu
uday.rao{at}uc.edu

This paper presents a quantitative model for telecommunication network installation by companies in the broadband-access business, specialized to the fixed-wireless case. Under stochastic demand modeled using scenarios, we maximize the expected demand coverage subject to a budget constraint on hub installation, and technological constraints on demand coverage by installed hubs. There are multiple hub types, differing in costs and capacities. We present a practical greedy heuristic based on the budgeted maximum-coverage problem and analyze its worst-case performance. For special cases with a single hub type or a single demand scenario, we show that a guarantee of 1 – 1/e or 63.2% applies to our greedy heuristic. For the general case we develop a data-dependent performance guarantee. Through computational experiments, we show that the greedy heuristic’s empirical performance is, on average, within 2% of the optimal expected demand coverage.

Key words: telecommunications; broadband access; fixed-wireless; location-allocation; network planning; stochastic programming; greedy approximation algorithms
History: received February 2003; revised August 2004; accepted November 2004.