A Unified Approach to Approximating Partial Covering Problems

A Unified Approach to Approximating Partial Covering Problems

0.00 Avg rating0 Votes
Article ID: iaor20112411
Volume: 59
Issue: 4
Start Page Number: 489
End Page Number: 509
Publication Date: Apr 2011
Journal: Algorithmica
Authors: , ,
Keywords: sets
Abstract:

An instance of the generalized partial cover problem consists of a ground set U and a family of subsets 𝒮 2 U equ1 . Each element eU is associated with a profit p(e), whereas each subset S 𝒮 equ2 has a cost c(S). The objective is to find a minimum cost subcollection 𝒮 𝒮 equ3 such that the combined profit of the elements covered by 𝒮 equ4 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 eU uncovered, we incur a penalty of π(e). The goal is to identify a subcollection 𝒮 𝒮 equ5 that minimizes the cost of 𝒮 equ6 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.

Reviews

Required fields are marked *. Your email address will not be published.