Analysis of the Greedy Approach in Covering Problems
Abstract
In this paper, we consider a general covering problem in which k subsets
are to be selected such that their union covers as large a weight of objects
from a universal set of elements as possible. Each subset selected must
satisfy some structural constraints. We analyze the quality of a k-stage
covering algorithm that relies, at each stage, on greedily selecting a subset
that gives maximum improvement in terms of overall coverage.
We show that such greedily constructed solutions are guaranteed
to be within a factor of 1 - 1/e of the optimal solution.
In some cases, selecting a best solution at each stage may itself be
difficult; we show that if a 
-approximate best solution is chosen
at each stage, then the overall solution constructed is guaranteed to be
within a factor of 1 - 1/e of the optimal.
Our results also yield a simple proof that the number of subsets used
by the greedy approach to achieve entire coverage of the universal set
is within a logarithmic factor of the optimal number of subsets.
Examples of problems that fall into the family of general covering problems
considered, and for which the algorithmic results apply, are discussed.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Analysis of the Greedy Approach in Covering Problems (14 pages, 203 KB)
,
- Dorit S. Hochbaum and Anu Pathria. To appear in Naval Research Quarterly.
dorit@hochbaum.ieor.berkeley.edu
7/30/98