×

A probabilistic analysis of the maximal covering location problem. (English) Zbl 0778.68046

Under a variety of different random models of the maximal covering location problem, we show that the relativ error of a randomly generated solution converges to zero in expectation as problem size grows. We prove similar results for the relative error between the optimal integer and fractional solutions to the problem. Suppose that randomly generated instances of this problem are used to test heuristics. One consequence 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.
Reviewer: Nicholas G.Hall

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahn, S.; Cooper, C.; Cornuejols, G.; Frieze, A.: Probabilistic analysis of a relaxation for the k-median problem. Math. oper. Res. 13, 1-31 (1988) · Zbl 0653.90049
[2] Belardo, S.; Harrald, J.; Wallace, W.; Ward, J.: A partial covering approach to siting response resources for major maritime oil spills. Management sci. 30, 1184-1196 (1984)
[3] Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. math. Statist. 23, 493-507 (1952) · Zbl 0048.11804
[4] Church, R.; Revelle, C.: The maximal covering location problem. Papers regional sci. Appl. 32, 101-118 (1974)
[5] Conforti, M.; Cornuejols, G.: Submodular functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado–edmonds theorem. Discrete appl. Math. 7, 257-274 (1984) · Zbl 0533.90062
[6] Garey, M. R.; Johnson, D. S.: Computers and intractibility: A guide to the theory of NP-completeness. (1979) · Zbl 0411.68039
[7] Hochbaum, D. S.: Easy solutions for the K-center problem or the dominating set problem on random graphs. Annals of discrete mathematics 25, 189-210 (1985) · Zbl 0562.68029
[8] A. Jain, Probabilistic analysis of LP relaxation bounds for the Steiner tree problem in networks, Networks, to appear. · Zbl 0682.90090
[9] Nemhauser, G. L.; Wolsey, L.: Maximizing submodular set functions: formulations and analysis of algorithms. Studies on graphs and discrete programming, 279-301 (1981) · Zbl 0469.90052
[10] C. Skiscim, Personal communication, 1986.
[11] Toregas, C.; Swain, R.; Revelle, C.; Bergman, L.: The location of emergency facilities. Oper. res. 19, 1363-1373 (1971) · Zbl 0224.90048
[12] Vercellis, C.: Probabilistic analysis of set covering. Ann. oper. Res. 1, 255-271 (1984) · Zbl 0671.90066
[13] R.V. Vohra and D. Foster, A probabilistic analysis of the K-location problem, Amer. J. Math., to appear. · Zbl 0776.90046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.