# zbMATH — the first resource for mathematics

Analysis of the greedy approach in problems of maximum $$k$$-coverage. (English) Zbl 0938.90026
Summary: The authors 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. They 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. They 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; they show that if a $$\beta$$-approximate best solution is chosen at each star, then the overall solution constructed is guaranteed to be within a factor of $$1-1/e^\beta$$ of the optimal.
These 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.

##### MSC:
 90B35 Deterministic scheduling theory in operations research 05C90 Applications of graph theory
##### Keywords:
$$k$$-stage covering algorithm; covering
Full Text: