Travelling salesman
Named by 4 essays across 3 fields — 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.
The shortest string holding every ordering
Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.
How close two sums of square roots come
Two different sums of square roots of whole numbers are never equal: square roots of different squarefree numbers are independent, so no cancellation can make them agree. But they can come very close. Among sums of two square roots of numbers up to 320, √88 + √289 and √171 + √177 agree to eight decimal places. How many digits must be computed, in the worst case, to tell two such sums apart is not known — the best proof allows a number of digits doubly exponential in the length of the sums, the examples suggest only a modest polynomial, and the gap between them is why nobody knows whether the shortest route through points in the plane can be checked quickly.
Named alongside it
The objects these essays reach for when they reach for this one.
RelaxationAlgebraic numberApproximation algorithmComplexityConjugateDe bruijn sequenceEulerian pathExhaustive searchGreedy algorithmHamiltonian pathIntegrality gapIrrationality