An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.