Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets ( S 2^E ), a total covering ratio q, each set (S S ) is associated with a cost (c_S ), each element (e E ) is associated with a covering requirement (r_e ), the goal is to find a minimum cost sub-collection ( S ' S ) to fully cover at least q|E| elements, where element e is fully covered if it belongs to at least (r_e ) sets of ( S ' ). Denote by (r_ = r_e:e E ) the maximum covering requirement. We present an ((O (r_ ^2n(1+ ( 1 )+ 1-q q )),1- ) )-bicriteria approximation algorithm, that is, the output of our algorithm has cost (O(r_ ^2 n(1+ ( 1 )+ 1-q q )) ) times of the optimal value while the number of fully covered elements is at least ((1- )q|E| ).
For the partial set cover problem, Kearns @cite_12 gave a greedy algorithm achieving performance ratio @math . By modifying the greedy algorithm a little, Slavik @cite_17 improved the performance ratio to @math , where @math is the percentage that elements are required to be covered. Gandhi @cite_23 proposed a primal-dual algorithm achieving performance ratio @math . Bar-Yuhuda @cite_5 studied a generalized version in which each element has a profit and the total profit of covered elements should exceed a threshold. Using local ratio method, he also obtained performance ratio @math . Konemann @cite_18 presented a Lagrangian relaxation framework and obtained performance ratio @math for the generalized partial set cover problem.
@cite_18 @cite_23 @cite_5 @cite_12 @cite_17
2901780026 2175530190 2046744707 1808619423
In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets ( S 2^E ), a cost (w_S ) on each set (S S ), a covering requirement (r_e ) for each element (e E ), and an integer k, the goal is to find a sub-collection ( F S ) to fully cover at least k elements such that the cost of ( F ) is as small as possible, where element e is fully covered by ( F ) if it belongs to at least (r_e ) sets of ( F ). On the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor (O(n^ 1 2( n)^c ) ) under the ETH assumption. A primal dual algorithm for MinPSMC is presented with a guaranteed performance ratio (O( n ) ) when (r_ ) and f are constants, where (r_ = _ e E r_e ) is the maximum covering requirement and f is the maximum frequency of elements (that is the maximum number of sets containing a common element). We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure. An instance of the generalized partial cover problem consists of a ground set U and a family of subsets @math . Each element e∈U is associated with a profit p(e), whereas each subset @math has a cost c(S). The objective is to find a minimum cost subcollection @math such that the combined profit of the elements covered by @math 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 @math that minimizes the cost of @math 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. In a STACS 2003 paper, Talwar analyzes the overpayment the VCG mechanism incurs for ensuring truthfulness in auctions. Among other results, he studies k-Set Cover (given a universe U and a collection of sets S 1 , S 2 , ? , S m , each having a cost c ( S i ) and at most k elements of U, find a minimum cost subcollection - a cover - whose union equals U) and shows that the payment of the VCG mechanism is at most k ? c ( OPT ' ) , where OPT ' is the best cover disjoint from the optimum cover OPT . The VCG mechanism requires finding an optimum cover. For k ? 3 , k-Set Cover is known to be NP-hard, and thus truthful mechanisms based on approximation algorithms are desirable. We show that the payment incurred by two mechanisms based on approximation algorithms (including the Greedy algorithm) is bounded by ( k - 1 ) c ( OPT ) + k ? c ( OPT ' ) . The same approximation algorithms have payment bounded by k ( c ( OPT ) + c ( OPT ' ) ) when applied to more general set systems, which include k-Polymatroid Cover, a problem related to Steiner Tree computations. If q is such that an element in a k-Set Cover instance appears in at most q sets, we show that the total payment based on our algorithms is bounded by q ? k 2 times the total payment of the VCG mechanism. We propose approximation algorithms under game-theoretic considerations. We indroduce and study the general covering problem which is a natural generalization of the well-studied max-n -cover problem. In the general covering problem, we are given a universal set of weighted elements E and n collections of subsets of the elements. The task is to choose one subset from each collection such that the total weight of their union is as large as possible. In our game-theoretic setting, the choice in each collection is made by an independent player. For covering an element, the players receive a payoff defined by a non-increasing utility sharing function. This function defines the fraction that each covering player receives from the weight of the elements. We show how to construct a utility sharing function such that every Nash Equilibrium approximates the optimal solution by a factor of @math . We also prove that any sequence of unilateral improving steps is polynomially bounded. This gives rise to a polynomial-time local search approximation algorithm whose approximation ratio is best possible.