Affordable Access

Publisher Website

A probabilistic analysis of the maximal covering location problem

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
43
Issue
2
Identifiers
DOI: 10.1016/0166-218x(93)90006-a

Abstract

Abstract Under a variety of different random models of the maximal covering location problem, we show that the relative 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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A decomposition approach for the probabilistic max...

on Computers & Operations Researc... Jan 01, 2009

A Lagrangean heuristic for the maximal covering lo...

on European Journal of Operationa... Jan 01, 1996

A note on solutions to the maximal expected coveri...

on Computers & Operations Researc... Jan 01, 2003
More articles like this..