1
$\begingroup$

In paper : https://arxiv.org/pdf/1908.00227.pdf it is stated that

In the metric TSP problem, which we study here, the distances satisfy the triangle inequality. Therefore the problem is equivalent to finding a closed Eulerian connected walk of minimum cost.

They don't seem to be equivalent at all, since for a complete graph of size 5, with all edge costs 1, a metric TSP solution would be of cost (and length) 5, whereas an Eulerian cycle would be of cost (and length) 10. Am I misunderstanding?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.