The greedy algorithm for monotone submodular maximization under a cardinality constraint (select k elements to maximize f) achieves approximation ratio (1 - 1/e). What drives this specific ratio?
AThe ratio comes from counting arguments about set sizes
BEach greedy step captures at least 1/k of the remaining gap to OPT (by submodularity, the best single addition is at least (OPT - f(S_i))/k). After k steps, the remaining gap is at most (1 - 1/k)^k * OPT ≈ OPT/e, so f(S_k) >= (1 - 1/e) * OPT
CThe ratio is an artifact of the analysis and the true guarantee is 1
DThe ratio depends on the specific submodular function and is not universal
Let S_i be the greedy set after i steps and S* be the optimal k-element set. By submodularity, the marginal gain of the greedy choice at step i+1 is at least (f(S*) - f(S_i))/k (because adding each element of S* to S_i gains at least as much as adding it to S* minus itself, and the greedy picks the best one). So f(S_{i+1}) - f(S_i) >= (OPT - f(S_i))/k, which gives f(S_k) >= (1 - (1-1/k)^k) * OPT >= (1 - 1/e) * OPT. The factor (1 - 1/k)^k -> 1/e is a fundamental quantity from the analysis of geometric convergence. Feige (1998) showed that (1 - 1/e) is optimal: no polynomial algorithm achieves a better ratio unless P = NP.
Question 2 True / False
Submodular MINIMIZATION (finding the set S that minimizes a submodular function f) can be solved in polynomial time, while submodular MAXIMIZATION under constraints is NP-hard.
TTrue
FFalse
Answer: True
This asymmetry is remarkable. Submodular minimization is equivalent to minimizing a convex function (the Lovász extension of a submodular function is convex), so it can be solved via convex optimization techniques — the Cunningham algorithm and the Iwata-Fleischer-Fujishige algorithm both achieve polynomial time. Submodular maximization, by contrast, includes MAX-CUT and maximum coverage as special cases, which are NP-hard. The greedy (1-1/e) approximation for monotone maximization and the double-greedy 1/2 approximation for unconstrained (non-monotone) maximization are the best possible. This mirrors the asymmetry in convex optimization: minimization is easy, maximization is hard.
Question 3 Short Answer
Explain why the maximum coverage problem (select k sets from a collection to maximize the number of covered elements) is a special case of submodular maximization, and what this implies about its approximability.
Think about your answer, then reveal below.
Model answer: Define f(S) = |union of sets in S| for a subcollection S of the given sets. This function is submodular because adding a set to a larger collection covers fewer NEW elements than adding it to a smaller collection (diminishing returns — elements already covered by the larger collection provide no additional benefit). It is also monotone (adding a set never decreases coverage). Maximum coverage asks to maximize this monotone submodular function subject to |S| <= k, so the greedy algorithm achieves (1-1/e)-approximation. Feige proved this is tight: no polynomial algorithm achieves (1-1/e+epsilon)-approximation for maximum coverage unless P = NP. This hardness result transfers to all monotone submodular maximization, making (1-1/e) the universal optimal ratio for this class.
Maximum coverage appears in facility location, sensor placement, influence maximization in social networks, and feature selection in machine learning. The clean (1-1/e) guarantee makes greedy the algorithm of choice for all these applications.
Question 4 True / False
The multilinear extension of a submodular function enables continuous relaxation techniques (analogous to LP relaxation) for submodular maximization under complex constraints.
TTrue
FFalse
Answer: True
The multilinear extension F(x) = E[f(R(x))] (where R(x) is a random set including each element i independently with probability x_i) extends the discrete submodular function to the continuous domain [0,1]^n. F is neither convex nor concave, but it is concave along positive directions (a consequence of submodularity). The continuous greedy algorithm (Calinescu et al.) maximizes F over a matroid polytope, then rounds the fractional solution using pipage rounding or contention resolution. This achieves (1-1/e)-approximation for monotone submodular maximization subject to matroid constraints — extending the greedy guarantee from cardinality to matroid constraints.