A probabilistic analysis of the maximal covering location problem (Q1801679)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A probabilistic analysis of the maximal covering location problem |
scientific article; zbMATH DE number 205584
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A probabilistic analysis of the maximal covering location problem |
scientific article; zbMATH DE number 205584 |
Statements
A probabilistic analysis of the maximal covering location problem (English)
0 references
4 January 1994
0 references
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.
0 references
approximation algorithms
0 references
random models
0 references
relativ error
0 references
heuristics
0 references
0 references
