Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that the resulting complete graph still satisfies the triangle inequality, and, of course, the TSP solution for the complete graph only uses original edges? Thank you.


If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.

  • $\begingroup$ A bit of nitpicking (sorry): If TSP is not metric, then the problem becomes probably harder. $\endgroup$
    – A.Schulz
    Jul 4 '13 at 7:16
  • $\begingroup$ @YuvalFilmus So, in my case, I cannot give weights to the non-edges such that the complete graph still satisfies the triangle inequality (infinite weight will violate this property)? $\endgroup$ Jul 4 '13 at 11:46
  • $\begingroup$ You might be able to choose weights that would make the graph satisfy the triangle inequality, but then a TSP tour could contain these edges. $\endgroup$ Jul 4 '13 at 14:17
  • $\begingroup$ @YuvalFilmus Can you shortly explain how to do that? (a TSP tour may contain one or more new edges.) Thank you. $\endgroup$ Jul 4 '13 at 17:02
  • 1
    $\begingroup$ If you start with a graph which doesn't falsify the triangle inequality, I think that you can give each missing edge the weight of the shortest path linking the two vertices, and then the result satisfies the triangle inequality. But I might be wrong on that. $\endgroup$ Jul 4 '13 at 17:51

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.