1978/08/01 by G. L. Nemhauser, George L. Nemhauser, L. A. Wolsey +1 · 25 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Cryptography and Data Security
paper · doi:10.1287/moor.3.3.177
openalex publication_date 1978/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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) ≥ z(S ∪ T) + z(S ∩ T), ∀S, T ⊆ N, and nondecreasing if z(S) ≤ z(T), ∀S ⊂ T ⊆ N. We consider the problem max S⊂N z(S): |S| ≤ 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 − 1. For fixed K, the qth member of this family requires O(n q+1 ) computations and is guaranteed to achieve at least [Formula: see text] 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 ).