Breaking the r_(max) Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

摘要

Given an element set E of order n, a collection of subsets S ⊆ 2~E, a cost c_S on each set S ∈ S, a covering requirement r_e for each element e ∈ E, and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection Fe ⊆S to fully cover at least k elements such that the cost of F is as small as possible and element e is fully covered by F if it belongs to at least r_e sets of F. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a (41og nH(Δ)In k + 2 log n n~(1/2))-approximation algorithm for MinPSMC, in which Δ is the maximum size of a set in S. And when k = Ω(n), we present a bicriteria algorithm fully covering at least (1 - ε/2log n) k elements with approximation ratio O(1/ε(log n)~2 H(Δ)), where 0 ＜ ε ＜ 1 is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself.