A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem (Q6049083)

This paper studies a bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem. The problem is studied with a profit on each element and it aims to find a minimum cost sub-collection of sets such that the profit of fully covered elements is at least \(q\)-percentage of total profit. A randomized \((O(b/q\varepsilon),1-\varepsilon)\)-bicriteria algorithm is presented. The algorithm produces a solution covering at least \((1-\varepsilon)q\)-percentage of the total covering requirement, and achieves performance ratio \(O(b/q\varepsilon)\) with a high probability, where \(b=\max_e\binom{f_e}{r_e}\) and \(f_e\) is the number of sets containing element \(e\) and \(r_e\) is its covering requirement. For the entire collection see [Zbl 1400.68037].