A minimum spanning tree is below the optimal tour, doubling it gives a walk, and shortcutting the walk gives a tour — but only if a direct hop is never longer than going round. That proviso is the triangle inequality and the panel has a slider that removes it. On the loaded instance the tree is 5, the tour is 10, the optimum is 7 and the ratio is 10/7, which is the worst ratio over all 482 metric instances on four cities with distances up to 3.
Core ideas
The first idea is where the lower bound comes from, which is a one-line argument about deleting an edge. The second is the step the hypothesis is doing work in. The third is what a small exhaustive sweep can and cannot say about a guarantee.
Take an optimal tour and delete any one of its steps. What remains visits every city and has no cycle, so it is a spanning tree, and its weight is less than the tour's. A minimum spanning tree is therefore no heavier than the optimal tour — a lower bound the algorithm computes with Prim's algorithm from the graph course, and the only thing the guarantee is proved against.
Walking every tree edge twice gives a closed walk of weight exactly 2 · MST visiting every city, but repeating cities. Shortcutting means skipping a city already visited and going straight to the next new one. That can only shorten the walk provided a direct hop is no longer than the path it replaces — which is exactly the triangle inequality. Without it the shortcut can cost more than the walk it replaces, and the panel's slider makes that happen.
The panel enumerates every symmetric instance on four cities with distances from 1 to 3, keeps the 482 satisfying the triangle inequality, solves each exactly, and reports the worst ratio: 10/7, which is about 1.43 against a promise of 2. The guarantee is not thereby shown to be loose. It quantifies over every size and every distance range, and the family swept here is tiny — four cities and three possible distances. A bound over all instances is not refuted by the worst of a finite few.
The material
The algorithm in three steps, the chain of four numbers, the measured ratio, the sweep over every small metric instance, and what happens when the hypothesis fails.
Distances are given for every pair of cities, are symmetric, and satisfy the triangle inequality: D(a,b) ≤ D(a,c) + D(c,b) for all a, b, c. The problem is to find a shortest tour visiting every city once and returning. Distances that come from positions in space always satisfy the inequality, which is why the hypothesis is usually free.
For distances satisfying the triangle inequality, the tour produced has length at most 2 · MST ≤ 2 · OPT.
Deleting one step from an optimal tour leaves a connected acyclic spanning subgraph, that is, a spanning tree, of weight at most the tour's. So MST ≤ OPT.
The doubled walk has weight exactly 2 · MST and visits every city. Shortcutting replaces a sub-path from a to b through already-visited cities by the direct hop D(a,b); by the triangle inequality applied along that sub-path, the hop is no longer than the sub-path it replaces. So the tour is at most 2 · MST, and combining gives 2 · OPT.
□
The loaded instance is four cities with the distances 1-2 2, 1-3 1, 1-4 3, 2-3 3, 2-4 2, 3-4 2, which satisfies the triangle inequality. The tree takes the edges of weight 1, 2 and 2 for a total of 5; the shortcut tour is 1, 2, 3, 4 at length 10; the optimum is 7, attained by 1, 2, 4, 3; and the realised ratio is 10/7. Notice that the tour equals 2 · MST exactly here, so the last link of the chain is an equality and all the slack in the promise lives in the gap between 5 and 7.
This instance was not chosen by hand. The panel enumerates every symmetric instance on four cities with distances from 1 to 3 — 729 of them — keeps the 482 that are metric, solves each exactly, and reports the worst ratio any produced. It is 10/7, and this is the instance attaining it. On three cities the same sweep reports a worst ratio of 1: the heuristic is exact there, because every tour on three cities is the same tour.
Load the instance with one distance raised: 1-2 50 with every other distance 1. The direct hop from 1 to 2 costs 50 while going round through 3 costs 2, so the triangle inequality fails by a factor of 25. The panel reports metric: no, a tree of 3, a promise of 6, an optimum of 4 — and a tour of 53, against a promise of 6. The answer is more than eight times the promise the algorithm made, because the shortcut step replaced a cheap path by an enormous hop and the proof's last line is simply false.
That is the most important thing on this page. A guarantee is a conditional, and when the condition fails there is no residual weaker guarantee: the algorithm can be arbitrarily bad, and the slider can make the ratio as large as you like. Raising the distance further raises the tour without limit while the optimum stays at 4.
And the general problem really is that bad, which was proved earlier on this course by putting ρ · n + 1 on the non-edges: no constant-factor approximation exists for the travelling salesman without a hypothesis, unless P = NP. So the triangle inequality is not a convenience that simplifies the analysis. It is the difference between a problem with a factor-2 algorithm and a problem with no constant-factor algorithm at all.
Interactive
The tree is below the optimum and the walk is twice the tree — and the shortcut step, the only one that needs the triangle inequality, is the one the slider breaks
Method
Four steps, and the first one is the only defence against a guarantee that does not apply.
Test the triangle inequality on every triple, which is what the panel's metric verdict is. Distances derived from coordinates always pass; distances that are prices, travel times with one-way roads, or measurements with noise may not, and a single violating triple is enough to void the guarantee.
The minimum spanning tree is not a by-product, it is the evidence. Report it beside the tour: the pair MST and 2 · MST brackets the answer, and it is the only bracket available when the optimum is out of reach.
On an instance small enough to enumerate, compute the optimum and divide. On a real instance you cannot, and then the honest report is the tour and the tree — a ratio against an unknown denominator is not a number.
482 metric instances on four cities with distances up to 3 give a worst ratio of 10/7. That is a fact about a small family, and it neither confirms nor threatens a bound of 2 over all families. The panel reports the family size precisely so the claim can be read at the right scope.
Distances 1-2 2, 1-3 1, 1-4 3, 2-3 3, 2-4 2, 3-4 2, every triple checked and metric. The tree is built by Prim's algorithm, unchanged from the graph course.
The shortcut here saves nothing: the walk weighs 10 and the tour is 10. That happens when the walk's repeated visits are all immediate backtracks, so the shortcut hops are the same edges the walk used. It is why this instance is the worst of the 482 — the algorithm pays the full 2 · MST while the optimum gets away with 7.
The optimum is 1-2-4-3, which uses the two edges of weight 2 and the edge of weight 1, avoiding the 3s. The tree also used the edge of weight 1, so the two solutions overlap; the tree is not a bad guess, it is simply a different object, and the factor of 2 is the price of turning one into the other.
For a faded rehearsal, load the instance the heuristic gets exactly right and predict the ratio before running it. The supplied first move: its distances are 3, 4, 5 on one side and 3, 4, 3 on the other, so the tree weighs 9 and twice the tree is 18. Say what the tour and the optimum have to be for the ratio to come out at 1, then check — and note that an instance where the ratio is 1 is as uninformative about the worst case as one where it is 10/7.
You should be able to build the tree, write the doubled walk, shortcut it, prove MST ≤ OPT by deleting an edge, identify the shortcut as the step needing the triangle inequality, test that inequality on given data, and state what survives when it fails.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.