Tours within half again of the best

A bound that may be off by a third approached the shortest tour from below: a linear programme whose optimum can be computed quickly and which the tour can never beat. This essay approaches it from above. If the shortest tour cannot be found quickly, a tour that is provably not much longer might be — and “not much longer” can be made exact, as a factor that holds for every instance.

Two such constructions are drawn here. The first walks twice around the shortest tree and is never more than twice the best tour. The second, found by Nicos Christofides in 1976 and independently by Anatoliy Serdyukov, adds one clever step and is never more than half as long again. Both need only one assumption about the distances, that a direct road is never longer than a detour — the triangle inequality — and both run in time polynomial in the number of cities.

The factor $\tfrac32$ turned out to be remarkably hard to beat. It stood as the best guarantee for any polynomial algorithm for forty-five years, and the reason it stood is connected to the gap in the relaxation: Laurence Wolsey showed in 1980 that Christofides’ tour is within $\tfrac32$ of the relaxation’s optimum, not merely of the shortest tour, which is where the upper bound of the previous essay came from.

Twice around the tree #

The shortest spanning tree — the cheapest set of roads connecting every city, with no loops — can be found quickly, by adding the cheapest road that joins a new city, one city at a time, as Robert Prim described in 1957. It is a lower bound on the shortest tour: delete any one road from a tour and what is left connects every city without loops, so it is a spanning tree, and it can be no shorter than the shortest one.

Now walk around the tree, as a child walks around the outside of a drawing, tracing every branch out and back. The walk uses every road of the tree exactly twice, so it costs twice the tree. It visits every city, some of them several times; skip every city already visited and go directly to the next new one. By the triangle inequality a skip never costs more than the stretch it replaces, so the resulting tour is at most twice the tree, and therefore at most twice the shortest tour.

In the figure the tree is 2.444, the tour made from it 4.193, and the shortest tour 3.461. The ratio is 1.21, well inside the guarantee of 2. On average the walk does much better than the guarantee, because the shortcuts save a great deal, but there are instances on which it comes arbitrarily close to twice the best, and the guarantee cannot be improved for this algorithm.

An Euler circuit needs even degrees #

The walk round the tree is wasteful because it doubles every road, and it doubles every road because an Euler circuit — a closed walk using every road exactly once — needs every city to have an even number of roads at it. That is the condition of seven bridges, and doubling the tree is a crude way to meet it: every degree doubles, and doubled numbers are even.

A tree already has many cities of even degree. Only the cities where it branches an odd number of ways fail the condition, and there is always an even number of those, since the degrees add up to twice the number of roads. Christofides’ idea is to fix only those. Pair up the odd cities and add one road for each pair: each odd city gains one road and becomes even, and the tree plus the pairing has an Euler circuit.

This is exactly the move of the streets a postman walks twice, where a postman who must walk every street finds the cheapest way to repeat streets so that every junction becomes even, by pairing up the odd junctions as cheaply as possible. The postman’s problem is to cover every road; the salesman’s is to visit every city; and the same pairing of odd degrees is the heart of both.

Tree, pairing, tour #

The algorithm has four steps, and the figure draws them. Find the shortest tree. Mark the cities of odd degree in it — six here. Find the cheapest perfect pairing of those cities, a problem Jack Edmonds showed in 1965 can be solved in polynomial time by his blossom algorithm. Add the pairing’s roads to the tree, find an Euler circuit of the result, and shortcut it to a tour. A walk that splices in its own detours described how to find the Euler circuit: start anywhere, walk until stuck, and splice in the loops not yet used.

The analysis is two sentences. The tree is shorter than the shortest tour. The pairing is at most half the shortest tour, because the shortest tour, shortcut to visit only the odd cities, is a cycle through an even number of cities, and taking alternate edges of that cycle splits it into two pairings whose total is at most the tour — so the cheaper of the two is at most half, and the cheapest pairing is no more. So the Euler circuit costs at most one and a half times the shortest tour, and the shortcuts only shorten it.

In the figure the pairing costs 1.531, less than half the shortest tour of 3.461, as the argument requires. The final tour is 3.607, only 4% longer than the best. Like the tree walk, the algorithm usually does far better than its guarantee.

Why the pairing can be found quickly #

The step that makes Christofides’ algorithm possible is the cheapest pairing, and it is not obvious that it can be found quickly. The number of ways to pair up $2m$ cities is $(2m-1)(2m-3)\cdots 3 \cdot 1$, which for forty odd cities is about $3 \times 10^{23}$. Trying them all is out of the question.

The natural shortcut is a linear programme: give each possible pair a weight between nought and one, require the weights at each city to add to one, and minimise the total length. For pairings between two separate groups — workers and jobs — that programme’s corners are all whole, and where the corners stop being whole showed exactly what goes wrong without the two groups: a triangle of cities, each pair at weight one half, satisfies every city’s condition and is no pairing at all. The corners stop being whole the moment odd cycles are allowed.

Jack Edmonds repaired it in 1965. For every odd-sized set of cities, at least one pair must leave the set — a pairing of an odd number of cities inside the set is impossible — and adding that condition for every odd set gives a programme whose corners are exactly the pairings. There are exponentially many such conditions, as there were subtour conditions for the salesman, but Edmonds’ blossom algorithm handles them implicitly, shrinking each odd cycle it meets into a single node and expanding it later, and runs in polynomial time. It was one of the first algorithms explicitly argued to be efficient because its running time grows polynomially, and the notion of polynomial time as the mark of an efficient algorithm is often traced to that paper.

So Christofides’ algorithm rests on two exact results about polytopes: that the spanning-tree polytope and the pairing polytope have the right corners, and that both can be optimised over quickly. Prices at every corner is the principle that makes the second fact useful: an optimum of a linear programme is always found at a corner, so a polytope whose corners are all pairings can be optimised over by linear programming without ever producing a fractional answer.

Measured against the best on forty instances #

On forty random instances of thirteen cities, all three quantities were computed exactly alongside the shortest tour. The relaxation from the previous essay is within one per cent below the tour on every instance and exact on most. Christofides’ tour averages 6.8% above the best, and its worst is 18.5% above. The tree walk averages 17% above and its worst is 45% above.

Those numbers sit far inside the guarantees. A guarantee is a statement about every instance, including the worst, and a random instance is rarely the worst. Practical tour-finding uses neither algorithm on its own: local improvements — swapping two roads for two others when that shortens the tour, as in the method of Shen Lin and Brian Kernighan — usually bring a tour within a few per cent of the best on instances of millions of cities, with no guarantee at all. The guaranteed algorithms matter for what they prove, and as starting points.

Other quick constructions have no constant guarantee. The nearest-neighbour rule, which always goes to the closest unvisited city, can produce tours that are longer than the best by a factor growing like the logarithm of the number of cities, as Daniel Rosenkrantz, Richard Stearns and Philip Lewis showed in 1977. The tree-based algorithms are guaranteed because each of their steps is compared with the shortest tour by an argument that holds for every instance.

A strip where the half is really lost #

Is the factor $\tfrac32$ an artefact of the analysis, or does the algorithm really lose that much? The strip in the figure answers it. Fifteen cities sit on two rows, arranged so that the shortest tree is the zigzag between the rows. A zigzag is a path, so its only cities of odd degree are its two ends, and the cheapest pairing is the single long road between them. Christofides’ tour follows the zigzag and returns along the long road: about one and a half times the length of the strip.

The shortest tour does something the tree never suggested. It runs along the top row and back along the bottom — about twice the length of the strip in one direction, but without the zigzag’s diagonals. Measured exactly, the algorithm’s tour is 20.208 and the best is 14.887, a ratio of 1.357 for fifteen cities, and as the strip lengthens the ratio approaches $\tfrac32$. The guarantee is tight: no better constant can be proved for this algorithm, because this instance defeats it.

The lesson is about what the tree knows. The zigzag is the cheapest way to connect the cities, and it is a terrible skeleton for a tour, because a tour must come back and the zigzag gives no cheap way to do so. Christofides’ pairing repairs the parity but not the geometry: it adds exactly the one road that makes a circuit possible, and that road is the longest in the instance.

The guarantee holds against the relaxation too #

The analysis above compared Christofides’ tour with the shortest tour. Laurence Wolsey noticed in 1980 that each step can be compared with the relaxation’s optimum instead. The tree is at most the relaxation’s optimum, because any solution of the relaxation, scaled by $\tfrac{n-1}{n}$, lies in the polytope whose corners are spanning trees. The pairing is at most half the relaxation’s optimum, because half of any solution of the relaxation lies in the polytope whose corners are pairings of the odd cities — a statement about fractional pairings that Edmonds’ description of the pairing polytope makes precise.

So Christofides’ tour is at most $\tfrac32$ of the relaxation’s optimum. The comparison is an instance of the principle in two numbers that have to meet: a feasible solution of one programme bounds the optimum of another, and here the relaxation’s solution, scaled, is feasible for both the tree programme and the pairing programme at once. Since the shortest tour lies between the relaxation’s optimum and Christofides’ tour, the shortest tour is also at most $\tfrac32$ of the relaxation’s optimum — which is the upper bound on the gap that the previous essay quoted. David Shmoys and David Williamson gave another proof in 1990, and it is the reason the two numbers $\tfrac32$, the algorithm’s guarantee and the relaxation’s worst gap, stood together for so long.

The figure checks the inequality on three families. The random instances sit near the corner where both ratios are 1. The two-triangle family sits far to the right — the shortest tour is well above the relaxation there — but Christofides’ tour is not much above the shortest. The strip sits high — Christofides does badly — but the relaxation is exact there, so the points stay at the left. No instance is bad in both ways at once, and none crosses $\tfrac32$.

Beating one and a half, by a hair #

For forty-five years no polynomial algorithm was known with a guarantee better than $\tfrac32$ for general distances obeying the triangle inequality. Better was known for special cases: for cities in the plane with straight-line distances, Sanjeev Arora and, independently, Joseph Mitchell showed in the late 1990s that tours within $1 + \varepsilon$ of the best can be found in polynomial time for any fixed $\varepsilon$; for distances along the roads of an unweighted graph, a sequence of results brought the factor to $1.4$.

In 2020 Anna Karlin, Nathan Klein and Shayan Oveis Gharan broke $\tfrac32$ for the general case, with an algorithm guaranteed within $\tfrac32 - 10^{-36}$ of the relaxation’s optimum. Their tree is not the shortest one but a random one, drawn from a distribution chosen so that each road appears with the probability the relaxation gives it; the odd cities of a random tree are less badly placed on average, and a delicate analysis shows the pairing then costs a little less than half. The improvement is tiny, and it proved that $\tfrac32$ is not a barrier.

The lower limit is further away than the upper. Marek Karpinski, Michael Lampis and Richard Schmied showed in 2015 that no polynomial algorithm can guarantee a factor better than $\tfrac{123}{122}$ unless P equals NP. Between $\tfrac{123}{122}$ and $\tfrac32 - 10^{-36}$ lies everything nobody knows.

Still open: the right constant #

Two constants are unknown and they may be the same. Both are about how far whole-number answers can lie from fractional ones — the question the lines the optimum lies under opened with a staircase and a roof — asked of the hardest problem it has been asked of. One is the best factor any polynomial algorithm can guarantee for tours obeying the triangle inequality; it lies between $\tfrac{123}{122}$, a hardness result, and $\tfrac32 - 10^{-36}$, an algorithm. The other is the worst gap of the subtour relaxation; it lies between $\tfrac43$, the two-triangle family, and the same $\tfrac32 - 10^{-36}$.

If the relaxation’s worst gap is $\tfrac43$, as conjectured, a $\tfrac43$-approximation algorithm is widely believed to follow, because every guarantee proved so far has come from rounding the relaxation’s optimum, and a proof that the gap is $\tfrac43$ would very likely be a rounding procedure. Whether the best algorithm can go below $\tfrac43$ — below what the relaxation can certify — is a different question, and would need a stronger bound than the relaxation provides.

What the pictures cannot show #

Every tour length here is exact: the shortest tours by Held and Karp’s dynamic programme, the relaxation by the simplex method with cuts, the pairings by an exact search over all pairings of the odd cities, which is feasible because there are only a few of them. For the random instances the ties that the algorithms face — two roads of equal length — are broken by the order of the cities, and a different tie-break gives a slightly different tour.

The strip’s ratio of 1.357 at fifteen cities is computed; its approach to $\tfrac32$ is the standard argument and is visible in the rising sequence, but a strip long enough to come within a per cent of $\tfrac32$ has far more cities than the exact tour computation can handle. The theorems of Christofides, Wolsey, Arora, Mitchell, Karlin, Klein and Oveis Gharan, and Karpinski, Lampis and Schmied are quoted; the figures check their conclusions on the instances drawn, and prove nothing beyond them.