In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first constructs a minimum spanning tree.

enter image description here

In order to prove this algorithm is a 2-approximation algorithm, the author claims that:

The weight of the minimum spanning tree $T$ is less than the cost of the optimal tour.

I am wondering if the minimum spanning tree(which is acyclic) of $G$ ensures that its weight is necessarily smaller than any tour(which is cyclic) of the same graph $G$


The original claim is:

enter image description here


1 Answer 1


If you take any tour and remove any edge, then you get a spanning tree. Hence the weight of a minimum spanning tree is at most the weight of every tour.

I should add that one of the tricks behind this algorithm is that while we can't find a minimum tour efficiently, we can find a minimum spanning tree. Minimum spanning tree is an efficiently computable relaxation of minimum Hamiltonian path.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.