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| ).
The set cover problem (SC) was one of the first 21 problems proved to be NP-hard in Karp's seminal paper @cite_11 . In fact, Feige @cite_19 proved that it cannot be approximated within factor @math unless @math , where @math is the number of elements. Dinur and Steurer @cite_9 proved the same lower bound under the assumption that @math . Khot and Regev @cite_1 showed that it cannot be approximated within factor @math for any constant @math assuming that unique games conjecture is true, where @math is the maximum number of sets containing a common element. On the other hand, greedy strategy achieves performance ratio @math @cite_13 @cite_4 @cite_22 , where @math is the maximum cardinality of a set and @math is the Harmonic number. And @math -approximation exists by either LP rounding method @cite_7 or local ratio method @cite_25 .
@cite_4 @cite_22 @cite_7 @cite_9 @cite_1 @cite_19 @cite_13 @cite_25 @cite_11
2001663593 2143996311 2890196309 2901780026
par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 . Given a collection F of subsets of S = 1,…, n , setcover is the problem of selecting as few as possiblesubsets from F such that their union covers S, , and maxk-cover is the problem of selecting k subsets from F such that their union has maximum cardinality. Both these problems areNP-hard. We prove that (1 - o (1)) ln n is a threshold below which setcover cannot be approximated efficiently, unless NP has slightlysuperpolynomial time algorithms. This closes the gap (up to low-orderterms) between the ratio of approximation achievable by the greedyalogorithm (which is (1 - o (1)) lnn), and provious results of Lund and Yanakakis, that showed hardness ofapproximation within a ratio of log 2 n 2s0.72 ln n . For max k -cover, we show an approximationthreshold of (1 - 1 e )(up tolow-order terms), under assumption that P≠NP . Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems. 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.