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| ).
In paper @cite_15 , Dobson first gave an @math -approximation algorithm for multi-set multi-cover problem (MSMC), where @math is the maximum size of a multi-set. Rajagopalan and Vazirani @cite_0 gave a greedy algorithm achieving the same performance ratio, using dual fitting analysis, which implies that the integrality gap of the classic linear program of MSMC is at most @math .
@cite_0 @cite_15
1988837529 2073127061
We build on the classical greedy sequential set cover algorithm, in the spirit of the primal-dual schema, to obtain simple parallel approximation algorithms for the set cover problem and its generalizations. Our algorithms use randomization, and our randomized voting lemmas may be of independent interest. Fast parallel approximation algorithms were known before for set cover, though not for the generalizations considered in this paper. We give a worst-case analysis for two greedy heuristics for the integer programming problem minimize cx , Ax (ge) b , 0 (le) x (le) u , x integer, where the entries in A, b , and c are all nonnegative. The first heuristic is for the case where the entries in A and b are integral, the second only assumes the rows are scaled so that the smallest nonzero entry is at least 1. In both cases we compare the ratio of the value of the greedy solution to that of the integer optimal. The error bound grows logarithmically in the maximum column sum of A for both heuristics.