Introduction

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)f(S) is submodular if, for any two sets A⊆BA \subseteq B and any element xx not in BB, adding xx to the smaller set AA gains at least as much as adding xx to the larger set BB:

f(A∪{x})−f(A)≥f(B∪{x})−f(B)f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)

The left side is the marginal gain of xx 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.

Try It: Sensor Placement

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: <strong id="budgetVal">6</strong> sensors
    <input type="range" id="budgetSlider" min="1" max="12" value="6">
  </label>
  <div class="btns">
    <button id="stepBtn" type="button">Step (Greedy)</button>
    <button id="runBtn" type="button">Run to budget</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="info-row">
  <span>Placed: <b id="placed">0</b> / <span id="budgetSpan">6</span></span>
  <span>Coverage: <b id="coverage">0</b> / 144 cells (<b id="pct">0</b>%)</span>
</div>
<div class="panel">
  <canvas id="grid" width="228" height="228"></canvas>
  <div class="sidebar">
    <div class="chart-title">Marginal gain per step</div>
    <canvas id="chart" width="160" height="180"></canvas>
    <div class="note" id="note">No sensors yet.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Greedy submodular maximization: sensor coverage on a 12x12 grid.
// f(S) = number of distinct cells within radius 2 of at least one sensor in S.
// Submodularity: marginal gain of each new sensor <= that of the previous one.
// Greedy guarantee: f(S_greedy) >= (1 - 1/e) * OPT for monotone submodular functions.
// Nemhauser, Wolsey & Fisher (1978).

const ROWS = 12, COLS = 12, RADIUS = 2;
const CELL = 19; // px per cell on canvas
const N = ROWS * COLS;

function idx(r, c) { return r * COLS + c; }

// Precompute which cells each sensor position covers (L-inf ball of radius 2).
function buildCover(sr, sc) {
  const s = new Set();
  for (let r = 0; r < ROWS; r++)
    for (let c = 0; c < COLS; c++)
      if (Math.abs(r - sr) <= RADIUS && Math.abs(c - sc) <= RADIUS) s.add(idx(r, c));
  return s;
}
const COVER = [];
for (let r = 0; r < ROWS; r++)
  for (let c = 0; c < COLS; c++) COVER.push(buildCover(r, c));

// State
let budget = 6;
let sensors = [];
let coveredSet = new Set();
let marginals = [];

function marginalGain(sensorIdx) {
  let gain = 0;
  for (const cell of COVER[sensorIdx])
    if (!coveredSet.has(cell)) gain++;
  return gain;
}

function greedyStep() {
  if (sensors.length >= budget) return false;
  let best = -1, bestGain = -1;
  for (let i = 0; i < N; i++) {
    if (sensors.includes(i)) continue;
    const g = marginalGain(i);
    if (g > bestGain) { bestGain = g; best = i; }
  }
  if (best === -1 || bestGain === 0) return false;
  sensors.push(best);
  for (const cell of COVER[best]) coveredSet.add(cell);
  marginals.push(bestGain);
  return true;
}

function reset() {
  sensors = []; coveredSet = new Set(); marginals = [];
  render();
}

const gridCanvas = document.getElementById('grid');
const gctx = gridCanvas.getContext('2d');
const chartCanvas = document.getElementById('chart');
const cctx = chartCanvas.getContext('2d');

function drawGrid() {
  gctx.clearRect(0, 0, gridCanvas.width, gridCanvas.height);
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const ci = idx(r, c);
      const x = c * CELL + 1, y = r * CELL + 1;
      const isSensor = sensors.includes(ci);
      const isCovered = coveredSet.has(ci);
      gctx.fillStyle = isSensor ? '#2a6496' : isCovered ? '#aecde3' : '#e8f0f7';
      gctx.strokeStyle = '#b0c4d8';
      gctx.lineWidth = 0.5;
      gctx.fillRect(x, y, CELL - 1, CELL - 1);
      gctx.strokeRect(x, y, CELL - 1, CELL - 1);
      if (isSensor) {
        gctx.fillStyle = '#fff';
        gctx.beginPath();
        gctx.arc(x + (CELL - 1) / 2, y + (CELL - 1) / 2, 3, 0, Math.PI * 2);
        gctx.fill();
      }
    }
  }
}

function drawChart() {
  const W = chartCanvas.width, H = chartCanvas.height;
  cctx.clearRect(0, 0, W, H);
  if (marginals.length === 0) return;
  const maxG = Math.max(...marginals, 1);
  const pad = { l: 28, r: 8, t: 10, b: 24 };
  const innerW = W - pad.l - pad.r;
  const innerH = H - pad.t - pad.b;
  const bw = Math.max(4, Math.floor(innerW / budget) - 3);
  // axes
  cctx.strokeStyle = '#b0c4d8'; cctx.lineWidth = 1;
  cctx.beginPath();
  cctx.moveTo(pad.l, pad.t); cctx.lineTo(pad.l, H - pad.b);
  cctx.lineTo(W - pad.r, H - pad.b);
  cctx.stroke();
  // y gridlines and labels
  cctx.fillStyle = '#6a8090'; cctx.font = '9px system-ui'; cctx.textAlign = 'right';
  for (const v of [0, Math.round(maxG / 2), maxG]) {
    const y = H - pad.b - (v / maxG) * innerH;
    cctx.fillText(v, pad.l - 3, y + 3);
    cctx.strokeStyle = '#e0e8ef'; cctx.lineWidth = 0.5;
    cctx.beginPath(); cctx.moveTo(pad.l, y); cctx.lineTo(W - pad.r, y); cctx.stroke();
  }
  // bars with color gradient (early=blue, late=orange)
  marginals.forEach((g, i) => {
    const t = i / Math.max(budget - 1, 1);
    const R = Math.round(42 + t * (210 - 42));
    const G = Math.round(100 + t * (130 - 100));
    const B = Math.round(150 + t * (40 - 150));
    cctx.fillStyle = `rgb(${R},${G},${B})`;
    const x = pad.l + i * (innerW / budget) + 2;
    const barH = (g / maxG) * innerH;
    cctx.fillRect(x, H - pad.b - barH, bw, barH);
    cctx.fillStyle = '#4a6070'; cctx.font = '9px system-ui'; cctx.textAlign = 'center';
    cctx.fillText(i + 1, x + bw / 2, H - pad.b + 12);
  });
}

function render() {
  budget = parseInt(document.getElementById('budgetSlider').value);
  document.getElementById('budgetVal').textContent = budget;
  document.getElementById('budgetSpan').textContent = budget;
  document.getElementById('placed').textContent = sensors.length;
  document.getElementById('coverage').textContent = coveredSet.size;
  document.getElementById('pct').textContent = Math.round(coveredSet.size / N * 100);

  const note = document.getElementById('note');
  if (sensors.length === 0) {
    note.textContent = 'No sensors placed yet. Click Step (Greedy) to begin.';
  } else if (sensors.length < budget) {
    const last = marginals[marginals.length - 1];
    note.textContent = fmt('Step %length%: +%last% new cells covered. Each bar shows the shrinking marginal gain.', { length: sensors.length, last: last });
  } else {
    const pct = Math.round(coveredSet.size / N * 100);
    note.textContent = fmt('Budget used. Coverage: %size%/%N% (%pct%%). Greedy guarantees ≥ 63.2 % of OPT.', { size: coveredSet.size, N: N, pct: pct });
  }

  document.getElementById('stepBtn').disabled = sensors.length >= budget;
  document.getElementById('runBtn').disabled = sensors.length >= budget;
  drawGrid();
  drawChart();
}

document.getElementById('budgetSlider').addEventListener('input', () => {
  budget = parseInt(document.getElementById('budgetSlider').value);
  if (sensors.length > budget) {
    sensors = sensors.slice(0, budget);
    marginals = marginals.slice(0, budget);
    coveredSet = new Set();
    for (const si of sensors)
      for (const c of COVER[si]) coveredSet.add(c);
  }
  render();
});
document.getElementById('stepBtn').addEventListener('click', () => { greedyStep(); render(); });
document.getElementById('runBtn').addEventListener('click', () => {
  while (sensors.length < budget) if (!greedyStep()) break;
  render();
});
document.getElementById('resetBtn').addEventListener('click', reset);
render();
Result
Console

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.

The Real Complexity

Maximizing a general set function requires checking all 2n2^{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=∅S = \emptyset.
  2. Repeat up to kk times: add to SS the element xx that maximizes f(S∪{x})−f(S)f(S \cup \{x\}) - f(S).
  3. Return SS.

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

f(Sgreedy)≥(1−1e)⋅f(OPT)≈0.632⋅f(OPT)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 1k\frac{1}{k} fraction of the remaining gap to OPT, so after kk steps the total gap shrinks by a factor of (1−1k)k\left(1 - \frac{1}{k}\right)^k, which converges to 1e\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.

Where It Matters

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 2n2^{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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/submodular-optimization/Content licensed under CC BY-NC 4.0.