Greedy algorithm
Named by 16 essays across 6 fields — each of them below, with the objects they name alongside it.
Every necklace, in order
The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.
The tree inside the triangulation
The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.
Twenty cards with no set among them
The card game SET is a four-dimensional space over the integers mod 3, and a set is a line in it. Twenty cards can avoid every line and twenty-one cannot — a fact that took a proof in 1970 — while laying cards down at random and stopping when nothing more fits reaches twenty about once in two thousand tries.
Matching as they arrive
Applicants arrive one at a time, and each must be given a post or turned away on the spot. Any sensible rule matches at least half as many as the best assignment chosen with hindsight, and an adversary arranging the arrivals can hold every fixed rule to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post: the guarantee rises to 1 − 1/e, about 63%, and no rule of any kind can do better.
The order decides the colours
The simplest way to colour a graph is to take the vertices one at a time and give each the first colour its neighbours are not already using. It never needs more than one colour beyond the largest degree — and on a graph that needs only two colours it can be made to use as many as there are vertices on a side, depending on nothing but the order it is handed.
Each user pays for its own last link
Several users must be connected to a source, and the cheapest network that does it is a tree. Dividing its cost so that no group of users would rather build its own looks like a hard search, and it has a one-line answer: each user pays for the link that joins it to the tree on its way to the source. No group is ever overcharged — while the average over orders of arrival, the rule that settles so much else, can charge a pair more than its own connection costs.
Matching when the arrivals are shuffled
An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.
Three circles that touch and are not the largest
In 1803 Gian Francesco Malfatti asked how to cut three round columns from a triangular block of marble with as little waste as possible, and answered with three circles each touching the other two and two sides. The circles exist in every triangle and are found by solving three equations. They are never the answer to his question: the plain greedy rule — the inscribed circle first, then the largest circle that still fits, twice — always does better, by 1.4 per cent on the equilateral triangle and by almost double on a thin one.
Three unit fractions for every four over n
Two neighbouring fractions in the tree always differ by a unit fraction, so stepping down the tree writes any fraction as a sum of them — four over n in at most four steps. Erdős and Straus asked in 1948 whether three always suffice. Three identities settle every n except those leaving remainder 1 on division by 24, a search settles every one anyone has tried, and nobody has a proof.
The boards a knight can tour
A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.
A spanning tree for every graph
Every connected graph has a spanning tree: a set of its edges that joins every point and closes no loop. For a finite graph the proof is a greedy pass over the edges. For an infinite graph the greedy pass has to keep going past the end of every list, and the statement turns out to be exactly as strong as the axiom of choice — Zorn's lemma supplies the tree, and the existence of spanning trees in every graph gives back the whole axiom.
One, plus a quarter, plus a ninth
Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.
The order that keeps elimination narrow
Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.
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.
The cheapest tree costs ζ(3)
Join n towns by every possible road, give each road a cost drawn at random between nought and one, and find the cheapest network of n − 1 roads that connects them all. However many towns there are, the bill tends to 1 + 1/8 + 1/27 + 1/64 + … = 1.2020569. The proof watches the cheap roads arrive one at a time and turns the cost into the area under a curve that counts the pieces of a growing random graph.
Five pyramids for every number
Stack balls in triangular pyramids and the piles hold 1, 4, 10, 20, 35, … balls. Frederick Pollock guessed in 1850 that every whole number is a sum of at most five such piles. Seventeen needs five — 10 + 4 + 1 + 1 + 1 — and so do 240 other numbers, the largest 343,867; past that, every number up to ten million needs four or fewer. Eight is proved to be enough. Five is not, and the reason is the same one that makes the three-dimensional cousins of the classical theorems hard.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchSpanning treeExpectationAlgorithmBipartite graphConjectureCounterexampleCounting argumentDe bruijn sequenceGraphLower boundMatching