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.