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 <tex-math>$z(S)+z(T)geq z(Scup T)+z(Scap T),forall S,Tsubseteq N$</tex-math>, and nondecreasing if <tex-math>$z(S)leq z(T),forall Ssubset Tsubseteq N$</tex-math>. We consider the problem <tex-math>${ m max}_{Ssubset N} {z(S)colon |S|geq K$</tex-math>, 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 <tex-math>$O(n^{q+1})$</tex-math> computations and is guaranteed to achieve at least <tex-math>$[1-(frac{K-q}{K})(frac{K-q-1}{K-q})^{K-q}]\times 100$</tex-math> 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 <tex-math>$O(n^{q+1})$</tex-math>.