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

摘要

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.