A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem.

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic (b / q ε , (1 − ε)) -bicriteria algorithm for SCPSMC, the output of which fully covers at least (1 − ε) q -percentage of the total profit and the performance ratio is b / q ε , where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e. [ABSTRACT FROM AUTHOR]