I was watching this video on the Travelling Salesman Problem (https://www.youtube.com/watch?v=GiDsjIBOVoA) and saw the following point discussed @ 8:55 :
This is my understanding of what the author is saying:
For a Travelling Salesman Problem with a large number of cities, it is impossible to find the optimal path (i.e. "tour") due to computational limitations. Therefore, it is also impossible to compare the quality (i.e. "cost") of a candidate solution to the Travelling Salesman Problem with the true optimal solution.
However, we have algorithms to find out the optimal Minimum Spanning Tree for problems with the same number of cities (e.g. Prim's Algorithm). And the cost for building the optimal Minimum Spanning Tree will always be less than the cost for the optimal Travelling Salesman Tour. Therefore, we can compare a candidate solution of the Travelling Salesman Problem to the optimal Minimum Spanning Tree - and since the cost for the optimal Minimum Spanning Tree is always less than the optimal Travelling Salesman Tour, we know that we will never be "generous" (i.e. overestimate the quality) in our comparison.
This brings me to my question:
The author of this video tried to visually demonstrate why the cost (i.e. summing the edge weights) for an Optimal Minimum Spanning Tree (with "n" nodes) will always be less than the cost of any Tour. However, I am not quite sure I understand this. Is there a mathematical proof that shows why the cost of an Optimal Minimum Spanning Tree will always be less than any Tour?
Should this above point be true, does this mean that there can exist some Sub-Optimal Minimum Spanning Trees that have higher costs than some candidate solutions to the Travelling Salesman Problem?
And finally, do we have anyway of knowing roughly how much "cheaper" the cost of an Optimal Minimum Spanning Tree is compared to the optimal Travelling Salesman Tour - or is this a contradiction by definition? For example, suppose the cost of the Optimal Minimum Spanning Tree is 52, the cost of our candidate solution is 485 and (suppose we could magically find out) the cost of the Optimal Travelling Salesman Tour is 483. Our analysis would tell us that our solution is not very good (52/485), but in reality our solution is pretty good (483/485) yet we have no way of knowing this. Is there someway to to approximately (e.g. probabilistically) quantify the maximum possible difference that can exist between the Optimal Travelling Salesman Tour and the Optimal Minimum Spanning Tree?
Thank you!
The idea for a proof that the MST cost is at most the TSP cost is in the screenshot you provided. Take an optimal TSP tour with cost $z_\text{TSP}$ and remove one edge, yielding a spanning tree with cost $z_\text{ST}$. Let $z_\text{MST}$ be the minimum spanning tree cost. Assuming nonnegative edge costs, we have $z_\text{MST} \le z_\text{ST} \le z_\text{TSP}$.
An even better lower bound on $z_\text{TSP}$ is obtained by computing a minimum $1$-tree, as shown by Held and Karp.
Assuming the edge costs satisfy the triangle inequality, you can double the minimum spanning tree edges and construct a tour that yields upper bound $z_\text{TSP} \le 2 z_\text{MST}$. See also https://en.wikipedia.org/wiki/Christofides_algorithm for a construction heuristic that yields a better upper bound $z_\text{TSP} \le 1.5 z_\text{MST}$.