Analysis of the greedy approach in problems of maximum k-coverage

Analysis of the greedy approach in problems of maximum k-coverage

0.00 Avg rating0 Votes
Article ID: iaor19992000
Country: United States
Volume: 45
Issue: 6
Start Page Number: 615
End Page Number: 627
Publication Date: Sep 1998
Journal: Naval Research Logistics
Authors: ,
Keywords: combinatorial analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.