Computing approximate solutions of the maximum covering
problem using GRASP

M. G. C. Resende

Journal of Heuristics, vol. 4, pp. 161-171, 1998.


We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.

PostScript file of full paper

PDF file of full paper

Mauricio G.C. Resende's Home Page

Last modified: 27 June 2002

Copyright Notice