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.

Authors

• Yishuo Shi
• Yingli Ran
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Ding-Zhu Du

Keywords

• Partial cover
• Multi-cover
• Submodular cover
• Bicriteria algorithm