Concept

Vertex enumeration

Listing the corners of a region carved out by linear constraints, by solving the systems of equations that hold with equality there. It is how a linear objective is maximised without calculus, since the best value is always taken at a corner.

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

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

applied · duality

A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · assignment

Named alongside it

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

Convexity Linear program Assignment Doubly stochastic Duality Existence proof Fairness Feasible region Matching Matrix Minimax Permutation

All concepts