Best Algorithms for Approximating the Maximum of a Submodular Set Function
(1978) Mathematics of operations research — Vol. 3, p. 177-188 (1978)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 454.21 KB
Details
- Authors
- Abstract
- 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}] imes 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>.
- Affiliations
Citations
Nemhauser, G. L., & Wolsey, L. (1978). Best Algorithms for Approximating the Maximum of a Submodular Set Function. Mathematics of operations research, 3, 177-188. https://hdl.handle.net/2078.5/32658 (Original work published 1978)