Approximation algorithms for submodular set cover with applications

The main problem considered is submodular set cover, the problem of minimiz ing a linear function under a nondecreasing submodular constraint, which ge neralizes both well-known set cover and minimum matroid base problems. The problem 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 c over variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for ea ch of them is either matching or generalizing the best existing bounds.