Proof that Christofides Algorithm is a 3/2-approximation for the TSP

156 Views Asked by At

I have quoted a section of the proof for the above statement, from Williamson and Shmoys. Can someone explain the section in italics?

"We want to show that the edges in the Eulerian Graph produced by the algorithm have total cost at most 3/2 OPT. We know that the minimum spanning tree edges have total cost at most OPT"

Is the fact that the min spanning tree edges have total cost at most OPT an easy result to notice, or is it related to some other theorem/property?

1

There are 1 best solutions below

0
On

Fact 1: Any spanning tree has weight at least of a minimum spanning tree.

Fact 2: The best possible Eulerian cycle is of weight OPT, hence any one of spanning tree it contains is of weight at most OPT.

Then a minimum spanning tree has weight less or equal to this OPT.

NB.I assumed, weights are non-negative.