Linear programming
Named by 11 essays across 3 fields — each of them below, with the objects they name alongside it.
The corners are whole assignments
A table of shares can be written as a lottery over whole assignments, which one worked example shows. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.
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.
Where the corners stop being whole
The easy theory of assignment rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.
Several colours on every vertex
Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.
Prices the bidders raise
The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.
The prices nobody can break away from
When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.
A bound that may be off by a third
The shortest tour through a set of cities is hard to find, and a linear programme gives a lower bound for it in polynomial time: give every road a weight between nought and one, two at each city, at least two across every division of the map. On random cities the bound is almost always exact. On two triangles joined by three long paths it falls short by nearly a third, and whether a third is the worst it can ever do has been conjectured for decades and never proved.
Prices for things wanted only together
When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.
A rent nobody envies is not one rent
Three housemates, three rooms, one rent, and Sperner's lemma promises a split nobody envies. It does not promise one split. For housemates who judge rooms by value for money, the envy-free splits fill a polygon, and in a typical house some room's rent can move across a quarter of the total without anyone envying anyone. Choosing inside it is a second decision. The rule the rent-splitting websites use makes the worst-off housemate as well off as possible, and in almost every house it rewards a housemate who understates what the rooms are worth.
A cube through a hole in a cube
Prince Rupert of the Rhine bet that a hole could be cut through a cube large enough for an equal cube to pass through it, and won. The trick is to look at the cube along a direction near its long diagonal, where its shadow is a hexagon wide enough to hold a square face with room to spare: a cube 6% larger can pass. All five Platonic solids turn out to have such a passage, found by searching over the directions from which a solid is seen — and in 2025 a solid was found that has none.
A relaxation that answers in halves
The cheapest set of points touching every edge of a graph is hard to find. Allow each point to be taken fractionally and the problem becomes a linear programme — and its best answers are never messier than halves. Every point gets 0, ½ or 1, the 0s and 1s can always be trusted, and the proof is a picture: double the graph into a bipartite one, where a matching decides everything exactly.
Named alongside it
The objects these essays reach for when they reach for this one.
AssignmentDualityMatchingMarket clearingPolytopeRelaxationAlgorithmCertificateComplementary slacknessConvexityCoreIntegrality