What is recorded here?
Nemhauser, Wolsey and Fisher established a sharp worst-case guarantee for greedily maximizing a nondecreasing submodular set function under a cardinality limit. Suppose you can choose only a few locations, services or resources. A greedy method adds the option that gives the greatest remaining benefit. This is simple, but usually does not find the exact optimum. The 1978 paper identified a reusable guarantee when benefit never decreases and has diminishing returns: an option becomes no more valuable when it is added to a larger existing selection. For a budget of K selections and zero benefit at the empty set, greedy achieves at least 1-(1-1/K)^K of the best possible value, approaching about63 percent for large K. The paper also supplied worst-case examples and analyzed separate local-swap, grouped-greedy, relaxation and partial-enumeration approaches. The guarantee concerns the stated benefit model, exact marginal comparisons and a limit on the number of selected elements. It does not cover arbitrary interactions, nonmonotone benefits or every resource constraint. Earlier facility-location results and matroid/submodularity theory remain distinct contributions.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The greedy approximation uses the stated finite-set, monotone submodular objective and cardinality constraints. Diminishing returns, feasibility and normalization assumptions matter. Nonmonotone functions and arbitrary constraints do not inherit the same guarantee. An approximation ratio is not exact optimization or measured practical performance.
Read the original work
- Nemhauser, Wolsey and Fisher, An analysis of approximations for maximizing submodular set functions-I,1978originaljournal CMUcoursecopy
- Springer publisherCrossrefdeposit for1978original
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
G. L. Nemhauser; L. A. Wolsey; M. L. Fisher
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Greedy selection: a guarantee when benefits have diminishing returns
Nemhauser, Wolsey and Fisher established a sharp worst-case guarantee for greedily maximizing a nondecreasing submodular set function under a cardinality limit.
Suppose you can choose only a few locations, services or resources. A greedy method adds the option that gives the greatest remaining benefit. This is simple, but usually does not find the exact optimum. The 1978 paper identified a reusable guarantee when benefit never decreases and has diminishing returns: an option becomes no more valuable when it is added to a larger existing selection. For a budget of K selections and zero benefit at the empty set, greedy achieves at least 1-(1-1/K)^K of the best possible value, approaching about63 percent for large K. The paper also supplied worst-case examples and analyzed separate local-swap, grouped-greedy, relaxation and partial-enumeration approaches. The guarantee concerns the stated benefit model, exact marginal comparisons and a limit on the number of selected elements. It does not cover arbitrary interactions, nonmonotone benefits or every resource constraint. Earlier facility-location results and matroid/submodularity theory remain distinct contributions.
Scientific scope
The greedy approximation uses the stated finite-set, monotone submodular objective and cardinality constraints. Diminishing returns, feasibility and normalization assumptions matter. Nonmonotone functions and arbitrary constraints do not inherit the same guarantee. An approximation ratio is not exact optimization or measured practical performance.
People and systems
G. L. Nemhauser; L. A. Wolsey; M. L. Fisher