A Unified Approach to Approximating Partial Covering Problems

An instance of the

generalized partial cover

problem consists of a ground set

U

and a family of subsets

${\cal S} \subseteq 2^U$

. Each element

e

∈

U

is associated with a profit

p

(

e

), whereas each subset

$S \in {\cal S}$

has a cost

c

(

S

). The objective is to find a minimum cost subcollection

${\cal S}' \subseteq {\cal S}$

such that the combined profit of the elements covered by

${\cal 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

∈

U

uncovered, we incur a penalty of

π

(

e

). The goal is to identify a subcollection

${\cal S}' \subseteq {\cal S}$

that minimizes the cost of

${\cal 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.