Concept

Triangle inequality

The rule that going directly between two points is never longer than going through a third. It holds for straight-line distance and defines a metric, and it is what lets a tour shortcut repeated visits without growing longer.

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

The parabola that proves |a·b| ≤ |a||b|. The squared length of a − t b plotted against t. It is a parabola opening upward whose least value is 7.118; that this is never negative is exactly the Cauchy–Schwarz inequality.

The square that cannot be negative

Cauchy–Schwarz is the load-bearing inequality of the whole subject and is nearly always stated without proof. It is one line away from a fact nobody would argue with, and the line is a parabola with no room to cross the axis.

algebra · Inner product

Christofides' algorithm: tree, pairing, tour. 12 cities: tree 2.4441, 6 odd cities paired for 1.5306, tour 3.6069, shortest 3.4606.

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.

applied · Duality

Named alongside it

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

Approximation algorithm Cauchy schwarz Discriminant Dot product Eulerian path Inequality Inner product Matching Norm Orthogonality Positive definite Projection

All concepts