Concept

Certificate

A short piece of data accompanying an answer that lets anybody verify it without repeating the computation. A set of dual prices certifies an assignment's optimality in a quadratic number of comparisons, against a factorial search.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

A largest flow of 5 through two wide ends and a narrow middle. A network with a capacity on every road, the amount a largest flow sends along each, and the cut whose capacity equals that flow's value drawn as a line separating the places.

The bottleneck is the whole story

However much a network can carry from one place to another, there is a way of cutting it in two whose total capacity is exactly that number. One quantity is a maximum over ways of routing and the other a minimum over ways of severing, and they are never off by even one.

discrete · Network flow

A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment

Named alongside it

The objects these essays reach for when they reach for this one.

Algorithm Assignment Bipartite matching Capacity Complementary slackness Conservation Cut Duality Edge disjoint paths Flow Linear programming Matching

All concepts