Continuous Greedy and Multilinear Extension for Matroid-Constrained Monotone Submodular Maximization

Continuous Greedy and Multilinear Extension for Matroid-Constrained Monotone Submodular Maximization is a two-stage continuous relaxation and rounding paradigm introduced by Calinescu, Chekuri, Pal, and Vondrak (2007, 2008, 2011) that achieves the optimal (1 - 1/e)-approximation for maximizing any monotone submodular set function f : 2^X -> R_+ subject to an arbitrary matroid constraint M = (X, I) in the value oracle model (Theorem 1.1), overcoming the tight 1/2-approximation barrier of the classical discrete greedy algorithm on general matroids (Fisher, Nemhauser, & Wolsey 1978). First, the discrete objective f is lifted to its canonical smooth monotone submodular multilinear extension F(y) = E[f(hat{y})] = sum_{R subseteq X} f(R) prod_{i in R} y_i prod_{j notin R} (1 - y_j) on [0, 1]^X (Section 2.1), which satisfies dF/dy_j = E[f(R + j) - f(R)] >= 0 (monotonicity), d^2F/(dy_i dy_j) <= 0 (submodularity, implying concavity along any nonnegative direction v >= 0), and d^2F/dy_j^2 = 0 (multilinearity, implying convexity along every swap direction e_i - e_j). Second, the Continuous Greedy algorithm integrates the flow dy/dt = v_max(y) = argmax_{v in P(M)} <v, grad F(y)> over t in [0, 1] starting from y(0) = 0 by iteratively finding a maximum-weight base I(t) in M with respect to sampled marginal gain estimates omega_j(t) = hat{E}[f_{R(t)}(j)] and updating y(t + delta) = y(t) + delta * 1_{I(t)} (Section 3.1), guaranteeing dF(y(t))/dt >= OPT - F(y(t)) and F(y(1)) >= (1 - 1/e) OPT in the matroid base polytope B(M) (Lemma 3.1, Lemma 3.3, Appendix A). Finally, matroid Pipage Rounding (Section 3.2, Lemma 3.5)—or independent per-block sampling for simple partition matroids (Section 3.3, Lemma 3.7)—exploits the convexity of F(y + t(e_i - e_j)) along tight-set swap directions to round y(1) to an integral independent base S in I with E[f(S)] >= F(y(1)) >= (1 - 1/e) OPT.