Approximation algorithms for submodular set cover with applications
Toshihiro Fujito · 2000
Introduction We start with the set cover( SC ) problem. Given a finite set M and a family N of subsets of M , a subfamily S of N is called a set cover if every element of M appears in some subset in S; in other words, the union of all subsets in S coincides with M . Each set in N is associated with a (U"C2T0"'# e) cost, and the cost of a family is the sum of costs of subsets in it. The set cover problem then asks to find a minimum cost set cover. As a special case when all the costs associated with sets are identical, it is called the unit cost set cover, and it is one of the basic NP-complete optimization problems presented by Karp [17]. he problem is also equivalent to the hitting set problem and the dominating set problem on gra