A Unified Approach to Approximating Partial Covering Problems

作者：Koenemann Jochen; Parekh Ojas; Segev Danny^*

来源：Algorithmica, 2011, 59(4): 489-509.

DOI：10.1007/s00453-009-9317-0

• Partial cover
• Approximation algorithms
• Lagrangian relaxation

An instance of the generalized partial cover problem consists of a ground set U and a family of subsets S subset of 2(U). Each element e is an element of U is associated with a profit p(e), whereas each subset S is an element of S has a cost c(S). The objective is to find a minimum cost subcollection S ' subset of S such that the combined profit of the elements covered by S ' is at least P, a specified profit bound. In the prize-collecting version of this problem, there is no strict requirement to cover any element; however, if the subsets we pick leave an element e is an element of U uncovered, we incur a penalty of pi(e). The goal is to identify a subcollection S ' subset of S that minimizes the cost of S ' plus the penalties of uncovered elements.
Although problem-specific connections between the partial cover and the prize-collecting variants of a given covering problem have been explored and exploited, a more general connection remained open. The main contribution of this paper is to establish a formal relationship between these two variants. As a result, we present a unified framework for approximating problems that can be formulated or interpreted as special cases of generalized partial cover. We demonstrate the applicability of our method on a diverse collection of covering problems, for some of which we obtain the first non-trivial approximability results.

• 出版日期2011-4