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 ^ ⊆ 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 (4 log nH(Δ)In k + 2 log n√n)-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 − _{2 log}^ε_n) k elements with approximation ratio O(¹_ε(log n)² 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.