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

✍ Scribed by Dorit S. Hochbaum; Anu Pathria

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 92 KB
• Volume: 45
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199809)45:6<615::aid-nav5>3.0.co;2-5

✦ Synopsis

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 0 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 b-approximate best solution is chosen at each stage, then the overall solution constructed is guaranteed to be within a factor of 1 0 1/e b 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.