· 16 min read
An Introduction to Submodularity
An introduction to submodular functions, the mathematical framework behind diminishing returns: set functions, marginal gains, and applications from sensor placement to influence maximization.
series/submodular-maximization
Submodular Maximization in Practice
Submodular maximization from intuition to working algorithms: what the property means, why greedy earns its (1 - 1/e) guarantee, and how lazy evaluation and stochastic sampling make it fast on massive datasets.
4 parts · complete
-
1 -
2 · 12 min readThe Greedy Algorithm for Submodular Maximization
The greedy algorithm achieves a (1 - 1/e) approximation for monotone submodular maximization, provably the best any efficient algorithm can do. This post covers the algorithm, its proof, and when greedy fails.
-
3 · 6 min readLazy Greedy: Speeding Up Submodular Maximization for Free
Lazy Greedy keeps the greedy algorithm's (1 - 1/e) guarantee while skipping most of its oracle calls. Submodularity makes stale marginal gains sound upper bounds, so a max-heap of them is enough to certify each pick.
-
4 · 9 min readStochastic Greedy: Scaling Submodular Maximization to Massive Datasets
Stochastic Greedy replaces greedy's full scan with random subsampling, reducing runtime from O(nk) to O(n ln(1/ε)) while losing only an additive ε in the approximation guarantee. This post covers the algorithm, its proof, and practical guidance.