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.

90B35 Deterministic scheduling theory in operations research
05C90 Applications of graph theory
Full Text: DOI