Submodularity
Diminishing returns for set functions, and greedy's (1 - 1/e) guarantee.
The idea
A submodular function is a set function with diminishing returns: the more a collection already holds, the less one further item adds. Coverage is the standard illustration. Suppose several sets each cover part of a ground set, and the score of a collection of them is the number of distinct elements their union covers. Adding one more set to a small collection contributes nearly everything it covers; adding the same set to a large collection contributes less, because much of what it covers is covered already.
Write $f(S)$ for the score of a collection $S$, and call $f(S \cup \{x\}) - f(S)$ the marginal gain of adding $x$ to $S$. The definition makes the shrinking of this gain precise.
Definition (Submodular function).
A set function $f : 2^{V} \to \mathbb{R}$ is submodular when, for all $A \subseteq B \subseteq V$ and every $x \notin B$, $f(A \cup \{x\}) - f(A) \;\ge\; f(B \cup \{x\}) - f(B).$
The smaller set is on the left, so adding $x$ to it gains at least as much as adding $x$ to the larger set. A separate property is monotonicity: $f$ is monotone when adding an item never lowers the score. Together the two properties carry a guarantee.
Theorem (Greedy guarantee).
Let $f$ be monotone and submodular, and let $k \ge 1$. The greedy rule — start from the empty set and repeatedly add the item of largest marginal gain until $k$ items are chosen — returns a set whose value is at least $(1 - 1/e)$ times the largest value of $f$ over all sets of at most $k$ items.
Here $1 - 1/e \approx 0.632$.
Algorithm.
Algorithm: Greedy Maximization Input: a monotone submodular function f on a ground set V, a budget k Output: a set of at most k items of V 1. S = the empty set 2. add to S the item x of V with the largest marginal gain f(S ∪ {x}) - f(S) // ties broken arbitrarily 3. if S has fewer than k items and an unchosen item remains, go to step 2 4. return S
Ways to work on it
- Walkthrough. Compute marginal gains on a coverage example and meet the (1 - 1/e) greedy guarantee.
- Practice. Compute a marginal gain or take a greedy step on random coverage instances.
- Hardest. Why greedy can miss the optimum, and which functions are submodular.
Not sure where to start? Take the ten-question placement test.