Relaxation
Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
Where the guarantee stops
Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.
When several pairs share the roads
For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.
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.
Tours within half again of the best
Nobody can find the shortest tour through many cities quickly, but a tour at most half as long again as the best can be built in a few steps: the shortest tree, a cheapest pairing of the cities where the tree branches oddly, an Euler circuit, and shortcuts. Nicos Christofides found it in 1976, and for forty-five years nobody could guarantee better. A strip of cities shows the half is really lost, and Laurence Wolsey's reading of the same argument shows it bounds the linear programme too.
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.
MatchingLinear programmingComplexityCounterexampleDualityIntegralityPolytopeTravelling salesmanApproximationApproximation algorithmAssignmentBipartite