Writing · Tagged
4 articles
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.
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.
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.
An introduction to submodular functions, the mathematical framework behind diminishing returns: set functions, marginal gains, and applications from sensor placement to influence maximization.