1
$\begingroup$

The penultimate step of the Christofides algorithm in solving the TSP asks us to find an Eulerian tour of the subgraph formed by uniting the MST of the original graph and MPM of a subgraph. I understand the starting point for the Eulerian tour will make a difference to the Hamiltonian circuit found after deleting the duplicate vertices in the next step. I am wondering if there is a way of finding what the best Euler tour would be? Or would you have to test every single one? This would seem inefficient for cases with lots of cities to visit.

Thanks for your help in advance!

Improve this question
$\endgroup$
2
  • $\begingroup$ You might want to look at: given a Eulerian circuit through all the nodes (sometimes repeating some), is there an algorithm to find the best Hamiltonian circuit (visiting each node just once) that "follows" the same order as the Eulerian circuit ("shortcutting"). What kind of problem is that? I don't know by the way..... $\endgroup$
    – TickaJules
    Commented Dec 16, 2021 at 13:54
  • $\begingroup$ I couldn't find a specific algorithm for this but felt like I was missing a logic step in the Christofides algorithm as it's used to solve really large problems to a good degree of accuracy. $\endgroup$
    – Jake Andrews
    Commented Dec 17, 2021 at 14:59

1 Answer 1

Reset to default
1
$\begingroup$

The problem of finding the minimum-weight cycle from the Euler tour computed by Christofides algorithm is called minimum-weight Christofides shortcutting problem [1]. Papadimitriou and Vazirani [2] prove this problem is NP-hard even for planar Euclidean TSP.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$
    – Jake Andrews
    Commented Dec 20, 2021 at 21:19

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.