Under a variety of different random models of the maximal covering loc
ation problem, we show that the relative error of a randomly generated
solution converges to zero in expectation as problem size grows. We p
rove similar results for the relative error between the optimal intege
r and fractional solutions to the problem. Suppose that randomly gener
ated instances of this problem are used to test heuristics. One conseq
uence of our results is that we should expect the mean relative error
of a heuristic to be better than that of randomly generated solutions,
if the heuristic is to be considered useful.