Best Algorithms for Approximating the Maximum of a Submodular Set Function

A real-valued function z whose domain is all of the subsets of N = {1,..., n} is said to be submodular if $z(S)+z(T)geq z(Scup T)+z(Scap T),forall S,Tsubseteq N$, and nondecreasing if $z(S)leq z(T),forall Ssubset Tsubseteq N$. We consider the problem ${ m max}_{Ssubset N} {z(S)colon |S|geq K$, z submodular and nondecreasing, z(φ) = 0}. Many combinatorial optimization problems can be posed in this framework. For example, a well-known location problem and the maximization of certain boolean polynomials are in this class. We present a family of algorithms that involve the partial enumeration of all sets of cardinality q and then a greedy selection of the remaining elements, q = 0,..., K - l. For fixed K, the qth member of this family requires $O(n^{q+1})$ computations and is guaranteed to achieve at least $[1-(frac{K-q}{K})(frac{K-q-1}{K-q})^{K-q}] imes 100$ percent of the optimum value. Our main result is that this is the best performance guarantee that can be obtained by any algorithm whose number of computations does not exceed $O(n^{q+1})$.