An analysis of approximations for maximizing submodular set functions—II

Abstract

Let N be a finite set and

a nonempty collection of subsets of N which have the property that

and F ₂⊂F ₁ imply

. A real-valued function z defined on the subsets of N that satifies z(S)≤z(T) for all S⊂T⊃-N and z(S)+z(T)≥(S∪T)+z(S∩T) for all S,T⊂-N is called nondecreasing and submodular. We consider the problem

, z(S) submodular and nondecreasing} and several special cases of it.

We analyze greedy and local improvement heuristics, and a linera programming relaxation when z(S) is linear. Our results are worst case bounds on the quality of the approximations. For example, when (N,

) is described by the intersection of P matroids, we show that a greedy heuristic always produces a solution whose value is at least 1/(P+1) times the optimal value. This bound can be achieved for all positive integers P.

Supported, in part, by NSF Grant ENG 76-20274.

Cornell University and supported, in part, by NSF Grant ENG 75-00568.