Wait, What?
A greedy algorithm can be provably near-optimal even when the exact optimisation problem is hard.
Submodular optimisation studies set functions with a diminishing-returns structure: adding one more item is valuable, but its marginal benefit usually falls as the selected set grows. This structure appears in coverage, sensor placement, summarisation, facility location, experimental design, influence spread and many machine-learning selection problems.
Quick Answer
Learn submodular optimisation through the route set functions → marginal gain → diminishing returns → monotonicity → greedy under a cardinality limit → approximation guarantee → lazy evaluation → knapsack constraints → matroid constraints → non-monotone objectives → continuous relaxations → large-scale implementation. The professional skill is to recognise when a hard combinatorial problem has enough structure to support a meaningful approximation guarantee.
1. Begin With a Set Function
A set function f maps a subset S of a ground set V to a number f(S). For example, V could be candidate camera locations and f(S) could measure how much of a building is visible from cameras placed at locations in S.
The decision problem is not “which single item is best?” It is “which subset gives the best total value under a constraint?”
2. Marginal Gain Is the Value of One More Item
Given a selected set S and a new item x, the marginal gain is f(S ∪ {x}) − f(S). It measures how much extra value x adds at this moment.
This “at this moment” matters. The same item can have a large gain when S is small and a tiny gain when S already covers most of what x would contribute.
3. Submodularity Means Diminishing Returns
A set function is submodular when adding an item to a smaller set gives at least as much marginal benefit as adding it to a larger set, assuming the item is not already selected.
Informally: the first few useful sensors, examples, documents or facilities often add a lot; later ones overlap with what has already been chosen.
4. Coverage Is the Best Beginner Example
Suppose each candidate sensor covers a subset of locations. Let f(S) be the number of unique locations covered by the sensors in S. The first sensor may cover 50 new locations. The fifth sensor may cover only 8 new locations because much of its region overlaps with previous sensors.
This makes the diminishing-returns property visible without heavy notation.
5. Monotonicity Is a Separate Property
A function is monotone when adding items never decreases the objective. Coverage is monotone: more sensors cannot reduce the number of covered locations.
Submodular does not automatically mean monotone. Keeping these concepts separate becomes important in advanced algorithms, because approximation guarantees change when adding an item can hurt the objective.
6. The Cardinality Constraint Creates a Classic Problem
A common task is: choose at most k items to maximise a monotone submodular function. Exact optimisation can be computationally hard, but the structure is strong enough for a remarkably simple greedy algorithm.
Start with the empty set. Repeatedly add the feasible item with the largest current marginal gain until k items have been chosen.
7. Greedy Is Not Exact, but It Has a Strong Guarantee
For monotone submodular maximisation under a cardinality limit, the classic greedy algorithm achieves a guarantee approaching 1 − 1/e of the optimum. This is one of the landmark results showing how structural properties can turn a simple heuristic into an approximation algorithm with a proof.
The foundational analyses are due to Nemhauser, Wolsey and Fisher. See An analysis of approximations for maximizing submodular set functions—I and Nemhauser and Wolsey, Best Algorithms for Approximating the Maximum of a Submodular Set Function.
8. Learn the Guarantee by Tracking What Remains
The proof idea is more important than memorising 1 − 1/e. At each step, compare greedy’s best available marginal gain with the total value still missing from an optimal solution. Submodularity lets us bound how much of that missing value can be recovered by one additional item.
Repeatedly shrinking the remaining gap gives the approximation bound. This is a powerful proof pattern: convert local progress into a global guarantee.
9. This Is Different From the General Greedy-Algorithm Lesson
The existing Greedy Algorithms article owns the broad question of when local choices lead to correct or incorrect solutions.
Submodular optimisation owns a narrower, deeper job: when exact optimality may be impossible or expensive, diminishing returns can still certify that greedy is close to optimal under specific constraints.
10. Approximation Ratio Must Be Interpreted Correctly
A 1 − 1/e guarantee does not say greedy always gets exactly 63.2% of optimum. It says the algorithm’s value is guaranteed to be at least that fraction in the worst case under the theorem’s assumptions; many real instances can be much better.
Never quote an approximation ratio without stating the objective class and constraint model that make it valid.
11. Lazy Greedy Avoids Recomputing Every Marginal Gain
Naive greedy recomputes every remaining candidate’s marginal gain after each selection. Submodularity tells us marginal gains can only fall as the selected set grows. A priority queue can therefore keep old gains as upper bounds and recompute only the candidates that might still be best.
This “lazy greedy” idea often reduces expensive objective evaluations dramatically while returning the same greedy solution.
12. The Objective Evaluation Can Dominate Runtime
In textbook pseudocode, f(S ∪ {x}) may look like one operation. In a real application, evaluating that marginal gain may require graph traversal, simulation, model inference or database access.
Professional implementation therefore counts objective evaluations, caches reusable state and distinguishes algorithmic iteration count from the true cost of evaluating the set function.
13. Knapsack Constraints Replace “Pick k” With a Budget
Items may have different costs. Instead of selecting at most k items, the algorithm may need total cost at most B. Now marginal gain alone can be misleading: a slightly weaker item may deliver much more value per unit cost.
This motivates cost-aware selection, partial enumeration and more advanced approximation methods.
14. Matroid Constraints Express Structured Feasibility
Some selection problems impose rules such as “at most one item from each category” or more general independence constraints. Matroids provide a mathematical language for families of feasible subsets with a useful exchange property.
Submodular maximisation under matroid constraints is richer than the simple cardinality case and leads to stronger algorithmic machinery, including continuous relaxations and rounding methods.
15. Non-Monotone Submodular Functions Are Harder
If adding an item can lower the objective, the simple greedy story breaks. Examples arise when selections create both benefits and penalties or redundancy costs.
Algorithms for non-monotone submodular maximisation use different techniques—randomisation, local search, double-greedy ideas, continuous methods—and the achievable guarantees depend strongly on the constraints.
16. Submodularity Is Often Called Discrete Convexity’s Relative
Submodular functions share several structural roles with convex functions, although the analogy must not be pushed too literally. Both provide enough shape to support strong optimisation results.
MIT’s advanced machine-learning material describes submodularity as a key tool for discrete optimisation and links it to structured prediction, greedy methods and scalable optimisation: 6.883 Advanced Machine Learning — Learning with Combinatorial Structure.
17. Applications Are About Diversity as Much as Value
Submodular objectives often reward broad coverage while naturally penalising redundant selections. This appears in document summarisation, selecting representative training examples, placing sensors, choosing facilities, active learning and recommendation.
An item can be individually strong but add little after similar items have already been chosen. That is the computational meaning of diminishing returns.
18. Connect This Topic to Existing Algorithm Foundations
The existing Approximation Algorithms article owns approximation ratios and proof discipline broadly. The Greedy Algorithms article owns general local-choice reasoning. Submodular optimisation connects both: a greedy procedure receives a nontrivial approximation guarantee because the objective has a specific diminishing-returns structure.
19. Common Learning Failure States
- Calling any function with decreasing values “submodular”.
- Confusing monotonicity with submodularity.
- Using greedy without checking the constraint and objective assumptions.
- Quoting 1 − 1/e as though it applies to every submodular problem.
- Recomputing expensive marginal gains unnecessarily.
- Ignoring item costs under budget constraints.
- Assuming a heuristic is an approximation algorithm without proving a bound.
- Benchmarking iteration count while objective evaluation dominates runtime.
20. A Beginner-to-Professional Learning Ladder
- Level 1: calculate coverage value for small sets.
- Level 2: compute marginal gains manually.
- Level 3: test diminishing returns on examples and counterexamples.
- Level 4: implement greedy under a cardinality constraint.
- Level 5: trace the residual-gap proof behind the approximation guarantee.
- Level 6: implement lazy greedy with a priority queue.
- Level 7: add item costs and study budget-aware selection.
- Level 8: model structured feasibility with matroid-style constraints.
- Level 9: study non-monotone and continuous-relaxation methods.
- Level 10: build a large-scale selector and evaluate objective quality, evaluation count, runtime and memory on real workloads.
21. Teach Marginal Gain Before Theorem Statements
Give learners a small coverage instance and ask them to predict the next greedy choice before running code. Then modify one overlap region and ask whether the marginal gain rises or falls. This Predict–Run–Investigate–Modify cycle mirrors PRIMM, a structured programming pedagogy supported by classroom research: Sentance, Waite and Kallia.
Use worked examples for the approximation proof before asking learners to derive it independently. Faded worked examples combined with metacognitive scaffolding have shown benefits in programming problem solving: Shin et al. (2023).
22. Immediate, Delayed and Transfer Checks
- Immediate: compute marginal gains for a coverage problem.
- Structure: test whether a small set function satisfies diminishing returns.
- Greedy: predict and then trace the selected sequence.
- Guarantee: explain why local progress can bound the remaining optimality gap.
- Delayed: reconstruct monotone, submodular, marginal gain and cardinality constraint without notes.
- Transfer: formulate sensor placement, document summarisation, facility coverage and representative-example selection as set-function problems.
23. AI Assistance Boundary
AI can generate toy set functions, produce greedy traces and help write benchmark harnesses. The learner should still be able to compute marginal gains, verify diminishing returns, state the exact assumptions behind an approximation guarantee, recognise when the objective evaluator dominates cost and defend the chosen constraint model independently.
Professional Direction
Advanced study includes submodular minimisation, non-monotone maximisation, matroid and knapsack constraints, continuous greedy, multilinear extensions, pipage and swap rounding, streaming submodular optimisation, distributed selection, adaptive submodularity, stochastic objectives, influence maximisation and submodular optimisation in machine learning.
Algorithm-learning rule: when each new item adds less value because earlier selections already cover part of its contribution, test for submodularity. That structure may turn a hard combinatorial search into an algorithm with a meaningful, provable quality guarantee.
eduKate Sengkang 