caa a22 4500 445804920 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9317-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9317-0 A Unified Approach to Approximating Partial Covering Problems [Elektronische Daten] [Jochen Könemann, Ojas Parekh, Danny Segev] An instance of the generalized partial cover problem consists of a ground set U and a family of subsets ${\mathcal{S}}\subseteq 2^{U}$ . Each element e∈U is associated with a profit p(e), whereas each subset $S\in \mathcal{S}$ has a cost c(S). The objective is to find a minimum cost subcollection $\mathcal{S}'\subseteq \mathcal{S}$ such that the combined profit of the elements covered by $\mathcal{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 $\mathcal{S}'\subseteq \mathcal{S}$ that minimizes the cost of $\mathcal{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. Springer Science+Business Media, LLC, 2009 Partial cover nationallicence Approximation algorithms nationallicence Lagrangian relaxation nationallicence Könemann Jochen Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Parekh Ojas Department of Mathematics and Computer Science, Emory University, 30322, Atlanta, GA, USA aut Segev Danny Sloan School of Management, MIT, 02139, Cambridge, MA, USA aut Algorithmica Springer-Verlag 59/4(2011-04-01), 489-509 0178-4617 59:4<489 2011 59 453 https://doi.org/10.1007/s00453-009-9317-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9317-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Könemann Jochen Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 700 1- Parekh Ojas Department of Mathematics and Computer Science, Emory University, 30322, Atlanta, GA, USA aut NATIONALLICENCE 700 1- Segev Danny Sloan School of Management, MIT, 02139, Cambridge, MA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 489-509 0178-4617 59:4<489 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer