D1 3.2 - Travelling salesman lower bounds

You already know

An upper bound comes from a feasible tour, and the smallest available upper bound is strongest. The complete shortest-distance network satisfies the triangle inequality. A minimum spanning tree minimises connection weight but need not be a tour.

Lower bound

If $T_{\min}$ is the optimal tour length, a valid lower bound $L$ satisfies

A larger valid lower bound is stronger. It need not be the length of any feasible tour.

Key idea

A lower bound proves that every tour costs at least that much. A drawn connection structure can establish a bound without itself being a Hamiltonian cycle.

Residual-tree lower bound

Delete node $V$ and all its incident arcs. Let $W_V$ be an MST weight on the remaining nodes, and let $a_V,b_V$ be the two least weights on distinct arcs incident to $V$ in the original complete network. Then

is a lower bound for the optimal tour length.

Not in the formula booklet: learn it.

Worked example 1: deleting A

Question. Use deletion of $A$ to obtain a lower bound for the tour length.

Plan. Find an MST on $B,C,D,E$, then add the two smallest distinct incident weights at $A$.

Prim from $B$ can select $BC,BE,CD$, each of weight $4$, giving

The two least $A$-incident weights are $AB=2$ and $AD=4$.

Why not add the two smallest weights anywhere in the original matrix? Both restored arcs must meet the deleted node $A$.

Answer. Deleting $A$ gives lower bound $18$.

Check. The residual tree includes exactly the four remaining nodes with three arcs. The restored connections go to two different neighbours of $A$.

Worked example 2: a stronger bound from another deletion

Question. Obtain a lower bound by deleting $E$.

Plan. Recompute an MST on $A,B,C,D$, then examine the original row for $E$.

An MST can use $AB,AD,BC$, with weight

The $E$-incident weights are $6,4,6,10$. The least two are $BE=4$ and either $AE=6$ or $CE=6$.

Why can either weight-$6$ arc be chosen? They are tied distinct alternatives for the second least incident weight; either gives the same lower bound.

Answer. Deleting $E$ gives lower bound $20$, stronger than $18$.

Check. $20$ is still no greater than the known feasible tour length $20$, so the bounds are consistent.

Watch out

Wrong: find an MST of the full network and add two arcs, or choose only one cheapest incident weight twice. Right: delete the node first, build the residual MST, then add two distinct original incident arcs.