A claim that an algorithm found a near-optimal traveling salesman tour only means something if the optimum, or a provable lower bound on it, is known. The standard yardstick since Held and Karp's 1970 paper is a bound built from minimum spanning trees with a penalty added to each city, which is cheap to compute and, in the test below, sat within about one percent of the optimum. With such a bound, a tour that is 5 percent above it is guaranteed to be at most 5 percent above the true optimum.
Key takeaways
- Every tour contains a spanning tree, so the weight of a minimum spanning tree is a lower bound on the optimal tour, though a weak one.
- A 1-tree bound is stronger, and Held and Karp (1970) showed how city penalties can raise it further without changing which tours are best.
- In an illustrative test on 12 random cities, the penalty-adjusted bound was 0.11 percent below the exact optimum on average, against 26.0 percent for a plain spanning tree.
- On 200 random cities, nearest neighbor ended 27.5 percent above that bound, 2-opt 8.8 percent, and 2-opt with Or-opt 4.7 percent.
- A reported gap is only as good as its denominator: proven optimum, lower bound, best known tour, or another heuristic.
Why a tour length alone says little
Tour length depends on the instance, so 11.2 units in one random map and 10.4 in another cannot be compared. What readers need is the gap: how much longer the tour is than the best possible one, as a percentage. The best possible length is usually unknown for large instances, since proving it needs a specialized exact solver. A lower bound fills the gap. If the optimum is at least B and a tour has length T, then the tour exceeds the optimum by at most (T minus B) divided by B. The bound turns an unknowable number into a guaranteed ceiling.
Two easy bounds
Delete any one edge from a tour and the remainder is a spanning tree, a set of edges that connects all cities without a loop. A tour therefore weighs at least as much as the cheapest spanning tree, which a greedy procedure such as Prim's algorithm finds quickly. That is the minimum spanning tree bound.
A 1-tree tightens it. Pick one special city. Build a minimum spanning tree on all the other cities, then add the two cheapest edges that touch the special city. Held and Karp describe a 1-tree as a tree plus one more vertex joined to it by two edges. A tour is a 1-tree in which every city has exactly two edges, so the cheapest 1-tree cannot be heavier than the best tour. Both bounds are still loose, because a spanning structure is free to give some cities many edges and others only one.
The Held-Karp penalty trick
The 1970 paper adds a number, a penalty, to each city and charges every edge the sum of the penalties at its two ends. A tour uses exactly two edges at each city, so every tour's cost rises by the same fixed amount, twice the sum of the penalties. The ranking of tours does not change. The cheapest 1-tree, however, does change, because trees can use cities unevenly. Subtracting the fixed amount gives a lower bound for every choice of penalties, and the paper defines the best of them as the strongest bound. The authors show it equals the optimal tour length exactly when a well-known linear program has an integer optimal solution, and they give an ascent method for computing it. In practice a subgradient method is used: after each trial, cities that received too many edges get a higher penalty, and cities that received too few get a lower one. The bibliographic record of the paper carries its abstract.
An illustrative test of how tight the bounds are
The figures come from a short script written for this article and are not a published benchmark. Cities were drawn uniformly in a unit square. For 12 cities, the exact optimum was found with Held-Karp dynamic programming on 20 instances, and each bound is shown as the percentage by which it falls short of that optimum. For 200 cities the optimum is unknown, so the penalty-adjusted bound, found with 400 subgradient steps on 10 instances, is the reference.
| Measure (illustrative) | Result |
|---|---|
| 12 cities: spanning tree bound below the optimum | 26.0 percent on average, up to 31.8 percent |
| 12 cities: plain 1-tree bound below the optimum | 16.0 percent on average, up to 27.5 percent |
| 12 cities: penalty-adjusted bound below the optimum | 0.11 percent on average, up to 1.18 percent |
| 200 cities: spanning tree and plain 1-tree bounds below the adjusted bound | 10.8 percent and 10.0 percent on average |
| 200 cities: nearest neighbor tour above the adjusted bound | 27.5 percent on average, range 20.2 to 34.4 percent |
| 200 cities: nearest neighbor followed by 2-opt | 8.8 percent on average, range 5.1 to 11.5 percent |
| 200 cities: 2-opt, then Or-opt, then 2-opt | 4.7 percent on average, range 2.2 to 6.0 percent |
The penalty-adjusted bound is far tighter than the others, and it is a guarantee for any random seed, even if the numbers shift. At 200 cities the true gaps in the last three rows are a little smaller than shown, because the bound itself lies below the optimum. These local-search methods are described in the entry on tour heuristics elsewhere on this site, and the point here is only how their quality is certified.
Reading a gap claim
A percentage gap can mean different things, and the denominator decides how much it proves.
- Gap to a proven optimum: the strongest claim, available only when an exact solver finished.
- Gap to a lower bound such as Held-Karp: a guaranteed ceiling on the true gap, slightly pessimistic.
- Gap to the best known tour: not a guarantee, since the best known tour may itself be improvable.
- Gap to another heuristic: a ranking of two methods, with no statement about optimality.
- No stated denominator: the number cannot be interpreted.
Learned solvers and commercial routing tools are often compared this way, so the denominator is the first thing to check in any such report.
FAQ
Why not just compare a new method with the best tour found so far?
Because that tour may be far from optimal. In the test above, measuring 2-opt against the best tour found by several heuristics gave gaps nearly five percentage points smaller than measuring against the bound.
Is the Held-Karp bound always below the optimum?
Yes. Every penalty setting produces a valid lower bound, so any value found by the ascent, even a rough one, is safe to use. A poorly tuned run only gives a weaker bound.
Does a small gap to the bound prove the tour is optimal?
No. A gap of zero would prove it. A small positive gap proves only that the optimum lies within that percentage.
Does the bound work for delivery routing with time windows?
Not directly. The 1-tree argument fits the plain symmetric traveling salesman problem. Vehicle routing with capacities and time windows needs other bounds, and many practical tools report no bound at all.
Related reading
- Families of algorithms for the salesman problem
- AI and route optimization for the salesman problem
- How AI approaches problem solving
- Hands-on AI learning at a camp
More in Traveling salesman problem.
Last verified: October 2026
Sources
- Held M, Karp RM. The Traveling-Salesman Problem and Minimum Spanning Trees, Operations Research 18(6), 1970
- Held M, Karp RM. A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics 10(1), 1962
- Croes GA. A Method for Solving Traveling-Salesman Problems, Operations Research 6(6), 1958