Submodular Optimization

Core Idea

A set function f: 2^V -> R is submodular if it satisfies diminishing returns: for all A subset B and element x not in B, f(A + x) - f(A) >= f(B + x) - f(B). Adding an element to a smaller set helps at least as much as adding it to a larger set. Submodular functions arise naturally in coverage (how many distinct customers are reached?), information gain (how much entropy is reduced?), and network influence (how many nodes are activated?). For monotone submodular maximization subject to a cardinality constraint, the greedy algorithm achieves approximation ratio (1 - 1/e) ≈ 0.632, and this is optimal unless P = NP. Submodular minimization (the dual problem) is solvable exactly in polynomial time via the Lovász extension and convex optimization — a surprising asymmetry between maximization and minimization.

Explainer

Submodularity is the discrete analog of concavity, and it appears wherever "diminishing returns" is a natural property. If f(S) measures the value of selecting set S, submodularity says that adding a new element to a small selection is at least as valuable as adding it to a large selection. This captures coverage functions (each new sensor covers some new area, but less as more are deployed), information-theoretic quantities (mutual information, entropy), and economic production functions.

The greedy algorithm for monotone submodular maximization under a cardinality constraint is remarkably simple: start empty, and repeatedly add the element with the largest marginal gain. The analysis shows that each step captures at least 1/k of the remaining optimality gap (where k is the cardinality bound), leading to geometric convergence that leaves at most a (1-1/k)^k ≈ 1/e fraction of the optimal value uncaptured. The resulting (1-1/e)-approximation is tight: Feige proved that no polynomial algorithm does better unless P = NP, via a reduction from MAX-3SAT. The greedy algorithm is optimal, and it is also dirt simple — a rare and satisfying coincidence.

The minimization side is strikingly different. Submodular minimization — finding arg min_S f(S) with no constraints — is solvable in strongly polynomial time. The key insight is the Lovász extension: every submodular function f has a convex extension to [0,1]ⁿ defined by f_L(x) = E[f(X_theta)] where X_theta = {i : x_i >= theta} for uniform theta in [0,1]. Minimizing f over subsets of V is equivalent to minimizing f_L over [0,1]ⁿ, which is a convex optimization problem. Algorithms based on the ellipsoid method or combinatorial approaches (Cunningham, Iwata-Fleischer-Fujishige) achieve polynomial time. This convexity of minimization versus the NP-hardness of maximization mirrors the broader landscape: finding valleys is easy, finding peaks is hard.

The continuous relaxation framework extends submodular optimization to complex constraints beyond cardinality. The multilinear extension F(x) extends f to the continuous cube [0,1]ⁿ, and the continuous greedy algorithm maximizes F over a polyhedral constraint (like a matroid polytope) using gradient ascent in the fractional domain. Rounding the fractional solution back to an integer set uses techniques like pipage rounding (which moves the fractional solution to a vertex while only increasing the objective) or contention resolution schemes. This framework achieves (1-1/e)-approximation for monotone submodular maximization subject to matroid constraints, unifying and extending the classical greedy result.