Approximation Algorithms for Submodular Set Cover with Applications

摘要

The main problem considered is submodular set cover, the problem of minimizing a linear function under a non- decreasing submodular constraint, which generalizes both well- known set cover and minimum matroid base problems. The prob- lem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.