Approximation algorithms

Read first

• Post 9: Construction heuristics. Nearest neighbour and the insertion heuristics build a full tour in a fraction of a second. On berlin52, nearest neighbour from city 1 lands 19.1% above the optimum. None of them says how bad the tour could be on a different instance.
• Primer A: graphs. You need four ideas from it. A spanning tree connects every vertex with no cycle. The minimum spanning tree (MST) is the cheapest one. The degree of a vertex is the number of edges touching it. A matching is a set of edges with no vertex in common, and it is perfect when it covers every vertex.

The question this post answers: can a fast algorithm promise that its tour is never more than a fixed factor worse than the optimum, on every instance?

Intuition

A heuristic’s gap is something you measure after the fact, and only when someone has already proved the optimum. An approximation algorithm comes with a proof instead: on every instance, its tour costs at most ρ times the optimum, where ρ is a fixed number called the approximation ratio.

The trick behind both algorithms in this post is to start from something whose cost we can relate to the optimum: the minimum spanning tree. Here are the same eight stops as in Post 1, with coordinates in kilometres. Distances are in units of 100 m, rounded, and the optimal tour costs 315.

The tree. In Post 1 we found the MST: A–G 36, A–B 41, B–C 36, C–D 41, D–H 28, D–E 36 and E–F 41, total 259. That number is already a lower bound on every tour. Delete any one edge from a tour and what is left is a path through all eight stops, which is a spanning tree. So every tour costs more than some spanning tree, and therefore at least as much as the cheapest one.

The double-tree algorithm turns the tree into a tour in two moves:

1. Walk around the tree. Start at A and do a depth-first walk, going down each branch and coming back. Every tree edge is used exactly twice, so the walk costs 2 × 259 = 518. I visit the branches at each stop in alphabetical order, so at D the walk goes to E (and F) before H.
2. Shortcut. The walk revisits stops. Keep each stop the first time the walk reaches it and jump straight to the next new stop.

Step through the diagram below to watch it happen. The lengths drawn are unrounded kilometres, so they differ from the matrix values by a few tenths.

The heatmap below prices that tour on the distance matrix. The outlined cells are the eight legs, and the strip underneath adds them up in driving order. The two shortcut legs, F→H at 91 and H→G at 72, are where the tour pays for jumping across the map.

The tour depends on the order of the walk. The tree has four distinct depth-first orders from A, and they give four different tours:

All four are within 2 × 259 = 518, which is the promise. One of them happens to be optimal, but the algorithm has no way to know which.

Christofides’ algorithm spends the doubling more carefully. Walking every tree edge twice is wasteful: the only reason to double edges is that a closed walk needs every stop to have an even number of edges. Christofides (1976) adds only what is missing.

1. Find the stops with an odd degree in the MST. Here they are D (degree 3), F, G and H (degree 1 each). There is always an even number of them.
2. Pair them up as cheaply as possible: a minimum-weight perfect matching. Four stops can be paired in three ways:

3. Add the cheapest matching to the tree. Now every stop has even degree, and the combined graph costs 259 + 70 = 329.
4. A connected graph where every degree is even has an Euler circuit: a closed walk that uses every edge exactly once. Walk it, then shortcut the repeats as before.

Step through the diagram below to see each stage.

The Euler circuit can also be walked in the other direction, A G F E D H D C B A. Shortcutting that gives A-G-F-E-D-H-C-B-A at 321, which is 1.02 times the optimum. Christofides promises 1.5, and both versions are well inside it.

The formal idea

Approximation ratio. For a minimization problem, an algorithm is a ρ-approximation if it runs in polynomial time and, on every instance I, returns a solution with cost ALG(I) ≤ ρ · OPT(I), where OPT(I) is the optimal cost. The ratio is a worst-case promise over all instances, not an average.

The triangle inequality. All the guarantees below assume d(i, k) ≤ d(i, j) + d(j, k) for every three cities: a direct trip is never longer than a detour. Distances with this property, together with symmetry, form a metric, and the problem is called the metric TSP. Shortcutting relies on it. Replacing the walk F → E → D → H by the direct leg F → H can only make the trip shorter when the triangle inequality holds.

Theorem (double tree, ratio 2). Let T be an MST and T* an optimal tour.

1. c(T) ≤ c(T*), because removing one edge from T* leaves a spanning tree.
2. The walk around the doubled tree costs exactly 2 · c(T).
3. Shortcutting never increases cost, by the triangle inequality.

So the double-tree tour costs at most 2 · c(T) ≤ 2 · OPT. The diagram below shows the chain of inequalities.

flowchart LR
  OPT["Optimal tour: OPT"] -->|"drop one edge"| MST["MST ≤ OPT"]
  MST -->|"use every edge twice"| W["Walk = 2 · MST"]
  W -->|"shortcut (triangle inequality)"| T["Tour ≤ 2 · MST ≤ 2 · OPT"]

The double-tree algorithm is folklore. Rosenkrantz, Stearns and Lewis (1977) proved the same factor of 2 for nearest insertion and cheapest insertion, by comparing them with the MST.

Theorem (Christofides, ratio 3/2). Let O be the set of odd-degree vertices of T and M a minimum-weight perfect matching on O.

1. c(T) ≤ OPT, as before.
2. c(M) ≤ OPT / 2. Take the optimal tour and shortcut it to visit only the vertices in O, in the same order. By the triangle inequality this cycle costs at most OPT. It has an even number of vertices, so its edges split into two perfect matchings on O by taking every other edge. The cheaper of the two costs at most half the cycle, and M is at least that cheap.
3. T plus M has only even degrees and is connected, so it has an Euler circuit of cost c(T) + c(M). Shortcutting does not increase it.

So the tour costs at most OPT + OPT/2 = 1.5 · OPT. Step 2 is the clever part, and the diagram below runs it on our example.

The whole algorithm is the pipeline below. Each step runs in polynomial time: the MST in O(n²), the matching with Edmonds’ blossom algorithm (1965), which later implementations by Lawler and by Gabow run in O(n³), and the Euler circuit in linear time.

flowchart TD
  A["Distance matrix (metric)"] --> B["Minimum spanning tree T"]
  B --> C["Odd-degree vertices O"]
  C --> D["Minimum perfect matching M on O"]
  D --> E["T + M: every degree even"]
  E --> F["Euler circuit, cost c(T) + c(M)"]
  F --> G["Shortcut repeated vertices"]
  G --> H["Tour ≤ 1.5 · OPT"]

The same result was found independently by Serdyukov in the Soviet Union and published in 1978. His paper was submitted in January 1976, before the date on Christofides’ report.

Why the triangle inequality is not optional. Suppose the road from F to H is closed and the only way around costs 500, while every other distance stays the same. The MST does not use F–H, so it still costs 259, and the optimal tour still costs 315. But the alphabetical double-tree walk still shortcuts from F to H, and its tour now costs 394 − 91 + 500 = 803: 2.55 times the optimum, past the factor of 2. The proof broke at its third step, because the direct leg F → H (500) is now longer than the detour F → E → D → H (105). On this modified matrix, 12 ordered triples of cities violate the triangle inequality.

Without the triangle inequality, no constant ratio is possible at all unless P = NP (Sahni and Gonzalez, 1976). The reason is the reduction from Post 2: give edges of a graph G cost 1 and all other pairs a huge cost. A ρ-approximation would then tell you whether G has a Hamiltonian cycle.

A practical footnote: rounding breaks the triangle inequality slightly. In berlin52’s rounded EUC_2D matrix, 80 triples of cities violate it, each by exactly 1 unit. The guarantees are proved for true metrics, so on rounded data a shortcut can, in principle, add a unit or two.

Limits of approximability. The table below summarizes what is known.

For more than four decades, Christofides’ 1.5 was the best known guarantee for the metric TSP. The 2021 improvement is real but tiny: a randomized algorithm with ratio 1.5 − ε for some ε > 10⁻³⁶. A 2024 follow-up pushed ε above 10⁻³⁴. The Euclidean schemes are a theoretical landmark, but their running times grow so fast as ε shrinks that they are not competitive with ordinary TSP heuristics, as Arora himself notes.

Common misconceptions

“A 1.5-approximation gives tours 50% above optimal.” It promises at most 50% above, in the worst case. On our eight stops Christofides found the optimum, and on berlin52 it lands 14.0% above it.

“A better guarantee means a better tour.” Not on a given instance. The ratio bounds the worst case only. On berlin52, Christofides (guarantee 1.5) beats nearest neighbour (no constant guarantee) by about five points, but on other instances the order can flip, and local search from Part 4 beats both by a wide margin.

“The MST is a tour with one edge missing.” The MST is a lower bound on the tour, not a piece of it. In our example the optimal tour uses six of the seven MST edges but not D–E, and it adds two edges the tree does not have, H–E and F–G.

“These guarantees hold for any distance matrix.” They need the triangle inequality. Real road networks mostly satisfy it, because the shortest path from i to k is never longer than going through j. Matrices built from tolls, penalties or hand-edited costs often do not.

Try it in Python

The script below runs both algorithms on berlin52 using only the standard library. The minimum matching is exact, found by dynamic programming over subsets of the odd-degree cities. That is exponential in the number of odd cities, but berlin52’s tree has only 22 of them, so it finishes in well under a second. Production code uses Edmonds’ blossom algorithm instead. The depth-first walk visits smaller city numbers first, and Prim’s algorithm breaks ties toward the lower city number, so the output is reproducible.

import math
from functools import lru_cache

def read_coords(path):
    body = open(path).read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
    return [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]

def mst_edges(d):
    """Prim's algorithm from city 0; ties go to the lower-numbered city."""
    n = len(d)
    best = {v: (d[0][v], 0) for v in range(1, n)}
    edges = []
    while best:
        v = min(best, key=lambda k: (best[k][0], k))
        _, u = best.pop(v)
        edges.append((u, v))
        for x in best:
            if d[v][x] < best[x][0]:
                best[x] = (d[v][x], v)
    return edges

def shortcut(walk):
    """Keep each city the first time the walk reaches it, then return to the start."""
    seen = list(dict.fromkeys(walk))
    return seen + [seen[0]]

def double_tree(d):
    edges = mst_edges(d)
    adj = {v: [] for v in range(len(d))}
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    walk, stack, seen = [], [0], set()
    while stack:                      # depth-first, smaller city numbers first
        v = stack.pop()
        if v in seen:
            continue
        seen.add(v)
        walk.append(v)
        stack.extend(sorted(adj[v], reverse=True))
    return shortcut(walk)

def min_perfect_matching(d, odd):
    """Exact minimum-weight perfect matching by dynamic programming over subsets."""
    @lru_cache(maxsize=None)
    def solve(mask):                  # mask = odd vertices still unmatched
        if mask == 0:
            return 0, ()
        i = (mask & -mask).bit_length() - 1          # lowest unmatched vertex
        best = None
        for j in range(i + 1, len(odd)):
            if mask >> j & 1:
                w, pairs = solve(mask & ~(1 << i) & ~(1 << j))
                w += d[odd[i]][odd[j]]
                if best is None or w < best[0]:
                    best = (w, pairs + ((odd[i], odd[j]),))
        return best
    return solve((1 << len(odd)) - 1)

def euler_circuit(n, edges, start=0):
    """Hierholzer's algorithm on a multigraph whose vertices all have even degree."""
    adj = {v: [] for v in range(n)}
    for k, (a, b) in enumerate(edges):
        adj[a].append((b, k))
        adj[b].append((a, k))
    used, stack, circuit = set(), [start], []
    while stack:
        v = stack[-1]
        while adj[v] and adj[v][-1][1] in used:
            adj[v].pop()
        if adj[v]:
            u, k = adj[v].pop()
            used.add(k)
            stack.append(u)
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

def christofides(d):
    edges = mst_edges(d)
    degree = [0] * len(d)
    for a, b in edges:
        degree[a] += 1
        degree[b] += 1
    odd = [v for v in range(len(d)) if degree[v] % 2]
    weight, matching = min_perfect_matching(d, odd)
    return shortcut(euler_circuit(len(d), edges + list(matching))), len(odd), weight

def length(tour, d):
    return sum(d[tour[i]][tour[i + 1]] for i in range(len(tour) - 1))

xy = read_coords("berlin52.tsp")
d = [[int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in xy] for p in xy]   # EUC_2D
OPT = 7542
mst = sum(d[a][b] for a, b in mst_edges(d))
dt = length(double_tree(d), d)
tour, n_odd, match = christofides(d)
assert sorted(tour[:-1]) == list(range(len(d)))
ch = length(tour, d)
print(f"minimum spanning tree:      {mst}")
print(f"double-tree tour:           {dt}  ratio to optimum {dt / OPT:.3f}  (guarantee 2)")
print(f"odd-degree cities in MST:   {n_odd}, minimum matching {match}")
print(f"Christofides tour:          {ch}  ratio to optimum {ch / OPT:.3f}  (guarantee 1.5)")

It prints:

Each tour sits under the bound its own proof gives, and far under the 2× and 1.5× ratios. Christofides is 14.0% above the optimum of 7,542, which beats nearest neighbour’s 19.1% from Post 2. The double tree is 37.9% above it. The guarantees are honest but loose: on this instance the actual tours are much better than promised.

If you run the same functions on the eight stops, they reproduce the hand-worked results: the double tree gives 394 and Christofides gives 315.

Exercise

Redo the double-tree walk on the eight stops, but at D visit H before E. Write out the full walk, shortcut it, and price the tour with the matrix above. Then check it against the promise: is it within 2 × 259?

Hint: the walk goes A, B, C, D, H, back to D, then E and F. The shortcut only matters at two points. Compare your answer with the table of four branch orders.

What this method can’t do yet

Look again at the double-tree tour A-B-C-D-E-F-H-G-A in the first diagram. The leg D–E crosses both F–H and H–G. A tour that crosses itself can always be shortened by uncrossing it, so this tour has an obvious, fixable flaw. The algorithm has no step that looks for it. It builds one tour and stops, and its guarantee is a ceiling on how bad things can get, not a promise of quality.

The same is true at scale. On berlin52, the double-tree tour has 14 pairs of edges that cross each other, and even the Christofides tour has 2. The optimal tour has none. Post 11, “Neighborhoods and the 2-opt move”, starts from any tour and fixes exactly this kind of flaw, one move at a time.

References

• Christofides, N. (1976). “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem.” Management Sciences Research Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University.
• Serdyukov, A. I. (1978). “On some extremal walks in graphs.” Upravlyaemye Sistemy 17: 76–79 (in Russian; English translation in van Bevern and Slugina, 2020).
• van Bevern, R., and Slugina, V. A. (2020). “A Historical Note on the 3/2-Approximation Algorithm for the Metric Traveling Salesman Problem.” Historia Mathematica 53: 118–127.
• Rosenkrantz, D. J., Stearns, R. E., and Lewis, P. M. (1977). “An Analysis of Several Heuristics for the Traveling Salesman Problem.” SIAM Journal on Computing 6(3): 563–581.
• Sahni, S., and Gonzalez, T. (1976). “P-Complete Approximation Problems.” Journal of the ACM 23(3): 555–565.
• Edmonds, J. (1965). “Paths, Trees, and Flowers.” Canadian Journal of Mathematics 17: 449–467.
• Edmonds, J. (1965). “Maximum Matching and a Polyhedron with 0,1-Vertices.” Journal of Research of the National Bureau of Standards 69B: 125–130.
• Lawler, E. L. (1976). Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.
• Arora, S. (1998). “Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems.” Journal of the ACM 45(5): 753–782.
• Mitchell, J. S. B. (1999). “Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems.” SIAM Journal on Computing 28(4): 1298–1309.
• Karpinski, M., Lampis, M., and Schmied, R. (2015). “New Inapproximability Bounds for TSP.” Journal of Computer and System Sciences 81(8): 1665–1677.
• Karlin, A. R., Klein, N., and Oveis Gharan, S. (2021). “A (Slightly) Improved Approximation Algorithm for Metric TSP.” Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 32–45.
• Gurvits, L., Klein, N., and Leake, J. (2024). “From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.” 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), LIPIcs 297, 79:1–79:20.
• Arora, S. (2003). “Approximation Schemes for NP-hard Geometric Optimization Problems: A Survey.” Mathematical Programming 97(1): 43–69.
• Williamson, D. P., and Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; berlin52 files and list of optimal solutions.

See the whole series · ← All writing