Submodular Optimization

Every child learns that the first bite of pizza is the best. The tenth is fine; the twentieth starts to feel like work. That intuition — each extra unit adds less value than the one before it — has a precise mathematical name: diminishing returns, and the functions that obey it are called submodular.

Formally, a set function $f(S)$ is submodular if, for any two sets $A \subseteq B$ and any element $x$ not in $B$, adding $x$ to the smaller set $A$ gains at least as much as adding $x$ to the larger set $B$:

$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$

The left side is the marginal gain of $x$ over the small set; the right side is the marginal gain over the big set. Submodularity just says the small-set gain is at least as large — value shrinks as the context grows.

This definition sounds abstract, but submodular functions appear everywhere: coverage in a sensor network, diversity in a recommendation list, information gain in experiment design, influence spread in a social network. Any time you are selecting a set of items and "more context means less extra value," submodularity is at work.

The question is: how do you maximize such a function subject to a budget? Picking the best k items from n candidates is already NP-hard in general — but submodularity changes everything.

Imagine a 12×12 grid of locations (144 cells). Each sensor you place covers every cell within radius 2 — a 5×5 square of up to 25 cells. You want to cover as many distinct cells as possible with a fixed budget of sensors. Coverage is a classic submodular function: the first sensor covers a full square; every additional sensor overlaps with previous ones, so its marginal gain is strictly smaller.

<div class="controls">
  <label>{{budget_label}}: <strong id="budgetVal">6</strong> {{sensors_label}}
    <input type="range" id="budgetSlider" min="1" max="12" value="6">
  </label>
  <div class="btns">
    <button id="stepBtn" type="button">{{step_btn}}</button>
    <button id="runBtn" type="button">{{run_btn}}</button>
    <button id="resetBtn" type="button" class="ghost">{{reset_btn}}</button>
  </div>
</div>
<div class="info-row">
  <span>{{placed_label}}: <b id="placed">0</b> / <span id="budgetSpan">6</span></span>
  <span>{{coverage_label}}: <b id="coverage">0</b> / 144 {{cells_of}} (<b id="pct">0</b>{{pct_suffix}})</span>
</div>
<div class="panel">
  <canvas id="grid" width="228" height="228"></canvas>
  <div class="sidebar">
    <div class="chart-title">{{chart_title}}</div>
    <canvas id="chart" width="160" height="180"></canvas>
    <div class="note" id="note">{{note_initial}}</div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1d2a38; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem 1.2rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .9rem; }
input[type=range] { width: 90px; accent-color: #2a6496; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border-radius: 7px; cursor: pointer;
         border: 1px solid #2a6496; background: #2a6496; color: #fff; }
button.ghost { background: #fff; color: #2a6496; }
button:disabled { opacity: .45; cursor: default; }
.info-row { display: flex; gap: 1.4rem; margin-bottom: .5rem; font-size: .9rem; flex-wrap: wrap; }
.panel { display: flex; gap: 1rem; align-items: flex-start; flex-wrap: wrap; }
canvas#grid { border: 1px solid #c8d4de; border-radius: 6px; display: block; }
.sidebar { flex: 1; min-width: 160px; }
.chart-title { font-size: .82rem; font-weight: 600; color: #4a6070; margin-bottom: .3rem; }
canvas#chart { border: 1px solid #e0e8ef; border-radius: 5px; background: #f7fafc; display: block; }
.note { font-size: .82rem; color: #55707e; margin-top: .5rem; line-height: 1.4; }

// Code not found

Click Step (Greedy) to let the algorithm pick the next sensor greedily — always choosing the location that covers the most new cells. Watch the marginal gain bar shrink with each step: that falling bar chart is diminishing returns made visible. Click Reset to start over, or Run to budget to place all sensors at once. The (1−1/e) guarantee means greedy reaches at least 63.2% of the theoretically best possible coverage — provably, for any grid and any budget.

Maximizing a general set function requires checking all $2^{n}$ subsets. Submodularity doesn't dissolve that hardness — maximizing a monotone submodular function subject to a cardinality constraint is still NP-hard, so no polynomial-time algorithm is expected to find the exact optimum.

What submodularity does give you is a provable approximation guarantee for the simplest algorithm imaginable:

The greedy algorithm (Nemhauser, Wolsey & Fisher, 1978):

1. Start with the empty set $S = \emptyset$.
2. Repeat up to $k$ times: add to $S$ the element $x$ that maximizes $f(S \cup \{x\}) - f(S)$.
3. Return $S$.

For any monotone submodular function (adding elements never hurts) and a cardinality budget $k$, greedy achieves:

$$f(S_{\text{greedy}}) \ge \left(1 - \frac{1}{e}\right) \cdot f(\text{OPT}) \approx 0.632 \cdot f(\text{OPT})$$

This bound is tight: no polynomial-time algorithm can do better unless P = NP (Feige, 1998). The proof uses a beautiful telescoping argument: each greedy step captures at least a $\frac{1}{k}$ fraction of the remaining gap to OPT, so after $k$ steps the total gap shrinks by a factor of $\left(1 - \frac{1}{k}\right)^k$, which converges to $\frac{1}{e}$.

For non-monotone submodular functions (dropping elements could help), the best known polynomial guarantee is 1/2, achieved by randomized local search.

Submodular minimization, by contrast, can be solved exactly in polynomial time — an elegant asymmetry that makes submodular functions one of the most beautifully structured objects in combinatorial optimization. The link to greedy algorithms and matroids runs deep here.

The greedy (1−1/e) guarantee is not just theoretical. It is actively used in production systems across many fields, because the submodular structure appears naturally wherever "more of the same helps less and less":

• Influence maximization: choosing k seed users in a social network to maximize expected spread. Kempe, Kleinberg & Tardos (2003) showed the spread function is submodular, making greedy the standard approach used by viral-marketing platforms.
• Document summarization: picking the k most informative sentences. Coverage and diversity objectives are submodular, so greedy outperforms random selection with a provable bound.
• Sensor placement and experimental design: maximizing the information gained by k measurements. The mutual information function is submodular for Gaussian processes, directly connecting to the demo above.
• Feature selection in machine learning: choosing k features that together explain a label. Submodular surrogates let you run greedy instead of exhaustive search over $2^{n}$ subsets.
• Budget allocation: distributing spend across channels to maximize total reach, where each channel has diminishing returns.

In all these cases, the same two-line greedy loop achieves (1−1/e) of optimal — a guarantee that linear programming relaxations sometimes can't match.

Submodular optimization is a rare place where a deep theorem and a trivially simple algorithm point at the same answer. The (1−1/e) guarantee proven by Nemhauser, Wolsey and Fisher in 1978 tells us: for any monotone submodular function, the greediest possible strategy — always pick what helps the most right now — is within 63% of whatever the best algorithm could ever do.

The falling marginal gains you watched in the sensor demo are not just a visual effect. They are the mathematical engine behind the proof, and behind every real-world application from viral marketing to feature selection.

Submodularity is one of those ideas that, once you see it, you recognize everywhere: in ecology, in economics, in information theory, in machine learning. And every time you spot it, you know that greedy is not just convenient — it is provably, irreversibly close to optimal. That is a rare and beautiful guarantee in a world where most optimization problems offer none at all. Compare it to the hopelessness of NP-hard problems where no such guarantee is known.