Randomized Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

Yishuo Shi, Zhao Zhang, Ding-Zhu Du

This paper studies randomized approximation algorithm for a variant of the set cover problem called minimum submodular cost partial multi-cover (SCPMC), in which each element $e$ h…