The Minima March Right

Some dynamic programs hide a table that is much larger than the thing you actually need from it.

You may only need, for every row,

argmin_j A[i,j]

but the obvious implementation still evaluates every A[i,j]. If the table is implicit and expensive, that is a strange kind of waste: the program spends most of its time proving that columns it did not need were not winners.

SMAWK is the sharper question for one important family of tables:

If the row minima have order, can we search the order instead of the table?

The Promise

A matrix is Monge for minimization when

\[A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j]\]

for all i < k and j < l. Read it as a no-crossing inequality: pairing the earlier row with the earlier column and the later row with the later column is no worse than crossing those assignments.

That inequality implies the leftmost row minima are nondecreasing. As the row index moves down, the best column can stay put or move right, but it cannot jump left.

The lab uses a generated family

\[A[i,j] = (j - s_i)^2 + \alpha_i + \beta_j,\]

where the centers satisfy s_i <= s_k for i < k. The Monge check is not mysterious:

\[\begin{aligned} &A[i,j] + A[k,\ell] - A[i,\ell] - A[k,j] \\ &\quad = 2(\ell-j)(s_i-s_k) \le 0. \end{aligned}\]

The row and column offsets alpha_i and beta_j change the values, but they cancel out of the inequality. That lets the lab tilt and shape the table without breaking the certificate.

What Total Monotonicity Adds

Plain monotone row minima are useful, but not enough for SMAWK. Aggarwal, Klawe, Moran, Shor, and Wilber’s matrix-searching paper separates the weaker condition from total monotonicity: every submatrix must have monotone row optima.¹

That submatrix clause is the engine. SMAWK deletes columns, recurses on a smaller set of rows, and then searches between neighboring answers. Those deleted-column subproblems must keep the same ordered-minima promise after rows and columns have been removed.

For Monge matrices, that promise survives because every submatrix is still Monge. Monge is stronger than SMAWK needs, but it is often how the structure appears in dynamic programs and geometry.²

Lab: Search Without Filling

The lab below compares two row-minimum algorithms on the same implicit matrix:

• brute force evaluates every cell;
• SMAWK uses only comparisons requested by its reduce-and-interpolate recursion.

The audit checks that the SMAWK minima match brute force, that the minima are nondecreasing, that every adjacent Monge inequality holds, and that SMAWK touches fewer unique cells than the full table scan.

The heatmap is drawn after the audit for explanation. The work counters measure only the metered lookups made by the search algorithms, not the pixels used to paint the matrix.

Scenario

wide convex drift

Wide convex drift Staircase optima Tall implicit table Sorted noisy centers Tilted column costs Rows

28

Columns

84

Column tilt

0.18

Seed

37

Row minima SMAWK-touched cells Generating center

Wide convex drift: leftmost row minima move from column 1 to 84. SMAWK matches brute force while touching 236 of 2,352 cells.

The Default Run

With the default 28 x 84 implicit matrix, the audited run reports:

Quantity	Value
brute-force cell evaluations	2,352
SMAWK unique cell evaluations	236
SMAWK comparisons	256
unique cells saved	90.0%
adjacent Monge violations	0
minima path	column 1 to column 84

You can run the wider regression grid from Node. It reports 35 named checks: seven invariants across five generated Monge-like matrices.

node - <<'NODE'
const lab = require("./assets/js/smawk-monge-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:wide:28x84:tilt=18:seed=37:2352/236:90.0:0:7/7",
  "2:staircase:40x92:tilt=-12:seed=19:3680/320:91.3:0:7/7",
  "3:tall:76x38:tilt=25:seed=41:2888/373:87.1:0:7/7",
  "4:jitter:44x88:tilt=0:seed=93:3872/294:92.4:0:7/7",
  "5:tilted:34x72:tilt=48:seed=11:2448/230:90.6:0:7/7"
];
const EXPECTED_CHECK_NAMES = [
  "SMAWK minima match brute force",
  "brute row minima are nondecreasing",
  "adjacent Monge inequalities hold",
  "SMAWK touches fewer cells than brute force",
  "all matrix values finite",
  "one minimum per row",
  "reduction never keeps more columns than rows at a level"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_NAMES.length;
const EXPECTED_CHECK_ROWS = Array.from({ length: EXPECTED_CASES }, (_, index) =>
  `${index + 1}:` + EXPECTED_CHECK_NAMES.map((name) => `${name}=true`).join("|")
);

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function checkNames(row) {
  return row.checks.map((check) => check.name);
}

function caseShape(row) {
  return `${row.caseId}:${row.scenario}:${row.rows}x${row.cols}:` +
    `tilt=${row.tilt}:seed=${row.seed}:` +
    `${row.bruteCells}/${row.smawkCells}:${row.savedPct.toFixed(1)}:` +
    `${row.mongeViolations}:${row.passedChecks}/${row.totalChecks}`;
}

function checkRow(row) {
  return `${row.caseId}:` +
    row.checks.map((check) => `${check.name}=${check.ok}`).join("|");
}

function rowDrifts(actual, expected) {
  return {
    missing: expected.filter((row) => !actual.includes(row)),
    extra: actual.filter((row) => !expected.includes(row))
  };
}

function hasRowDrift(drift) {
  return drift.missing.length > 0 || drift.extra.length > 0;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const shape = {
  cases: audit.cases.map(caseShape),
  checkRows: audit.cases.map(checkRow)
};
const checkRowDrifts = rowDrifts(shape.checkRows, EXPECTED_CHECK_ROWS);
const shapeErrors = [];
if (!sameList(shape.cases, EXPECTED_CASE_SHAPE)) {
  shapeErrors.push({ name: "cases", actual: shape.cases, expected: EXPECTED_CASE_SHAPE });
}
audit.cases.forEach((row) => {
  const names = checkNames(row);
  if (!sameList(names, EXPECTED_CHECK_NAMES)) {
    shapeErrors.push({
      name: `case ${row.caseId} check names`,
      actual: names,
      expected: EXPECTED_CHECK_NAMES
    });
  }
});
if (hasRowDrift(checkRowDrifts)) {
  shapeErrors.push({ name: "checkRows", drift: checkRowDrifts });
}
console.table(audit.cases.map((row) => ({
  scenario: row.scenario,
  rows: row.rows,
  cols: row.cols,
  bruteCells: row.bruteCells,
  smawkCells: row.smawkCells,
  savedPct: row.savedPct.toFixed(1),
  mongeViolations: row.mongeViolations,
  checks: `${row.passedChecks}/${row.totalChecks}`,
  passed: row.passed
})));
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  !audit.ok ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    checkRowDrifts,
    failed,
    errors: audit.errors,
    totals: {
      total: audit.total,
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}
console.log(summary);
NODE

The grid covers wide, tall, tilted, staircase, and jittered Monge instances. It is a regression harness for this implementation, not a substitute for the total-monotonicity proof.

The exact numbers are not universal. They depend on the table shape and on the implementation’s caching policy. The important fact is structural: the brute force method scales with rows * columns, while SMAWK’s recursion keeps asking only the cells needed to preserve the ordered-minimum certificate.

The Two Moves

SMAWK has two recurring moves.

First, reduce columns. Scan columns left to right with a stack of surviving columns. A comparison at one row can prove that a previous column cannot be the leftmost minimum for any row that remains in this level’s subproblem. The stack ends with at most as many columns as active rows.

Second, interpolate rows. Recursively solve every other row. If row i-1 has minimum column a and row i+1 has minimum column b, total monotonicity says row i only needs to search columns from a through b.

That is the whole personality of the algorithm: delete columns globally, recurse on half the rows, and fill the gaps locally.

In the default run, the first reduction level shrinks 84 columns to 28. The next levels shrink 28 -> 14, then 14 -> 7, then 7 -> 3, then 3 -> 1. Those are not approximations. The final row minima still match the full table scan exactly.

Where This Shows Up

The original SMAWK paper is written in a row-maximum convention and uses the algorithm for geometric problems such as all-farthest neighbors of convex polygon vertices.¹ Minimization is the same idea after changing signs or reversing the inequality.

In dynamic programming, the hidden matrix is often a transition-cost table:

\[dp[i] = \min_j \{ previous[j] + cost(j,i) \}.\]

If the induced table is Monge or totally monotone, the best predecessor indices move in order. Then a layer of DP can sometimes be computed by searching row minima rather than scanning every predecessor for every state.

That last sentence hides the hard part. The Monge property is a mathematical claim about the cost function, not a vibe from a plot. Before replacing a full scan with SMAWK, I would want a proof, a property test for generated instances, and a brute-force audit on small cases.

Boundaries

SMAWK is exact under its assumptions. It is not a heuristic for any matrix whose argmins happen to look smooth.

Three failure modes matter:

1. The full matrix has monotone row minima, but a submatrix does not. SMAWK may delete a column that becomes necessary after other columns are removed.
2. The tie-breaking rule is inconsistent. This lab uses leftmost minima and strict replacement so equal values keep the earlier column.
3. The matrix-entry function is not actually constant time. SMAWK reduces the number of entries requested, but if each entry hides a large computation, the entry function still deserves profiling.

The useful mental model is small:

Monge inequality -> total monotonicity -> ordered row minima
ordered subproblems -> reduce columns + interpolate rows

The minima march right. SMAWK notices that they do not need a full parade route.

Sources

1. Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber, “Geometric Applications of a Matrix-Searching Algorithm”, Algorithmica 2, 195-208, 1987. Publication records: IBM Research, DOI. ↩ ↩²

2. Rainer E. Burkard, Bettina Klinz, and Rudiger Rudolf, “Perspectives of Monge Properties in Optimization”, Discrete Applied Mathematics 70(2), 95-161, 1996. ↩