1
$\begingroup$

How do I do the change from an Eulerian tour to a Hamiltonian cycle in the Christofides algorithm? In the original paper from Christofides (1976)1 I found that

A Hamiltonian circuit $i$ of $G$ can be found with cost $$C(i_H) \le C(T^*) + C(M_0^*)<\frac32C(i^*)$$ where $C(i^*)$ is the optimal value of the TSP tour $i^*$.

On cs.stackexchange.com I found this answer:

However, we wanted a Hamilton cycle (another name for a TSP tour). The idea now is to follow the Eulerian tour. Whenever we're supposed to visit a vertex we have already encountered, we just "skip" this edge. Eventually the tour will reach a new vertex, and then we just connect the previous vertex with the new one.

Are there not more than one possible Hamiltonian cycle in one Eulerian tour? Is it good enough to take just some Hamiltonian cycle? Does this already satisfy the upper bound of $3/2$?


Reference

[1] Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group.

$\endgroup$
4
$\begingroup$

The weight sum of all edges in the Eulerian tour created in Christofides algorithm is already at most $3/2$ times the weight sum of a TSP tour. While there are multiple ways of shortcutting the Eulerian tour into a Hamiltonian cycle, note that by the triangle inequality, any shortcut edge has a weight that is less than the total weight of the edges in the Eulerian tour it replaces. So, any Hamiltonian cycle created by shortcutting the Eulerian tour yields a $3/2$-approximate solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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