Travelling salesman
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
RelaxationApproximation algorithmEulerian pathIntegrality gapLinear programmingMatchingMinimum cutPolytopeSpanning treeTriangle inequality