Talk:Christofides algorithm

Latest comment: 7 years ago by 195.176.111.6 in topic Approximation wrong

Approximation wrong

edit

I think the matching on the optimal solution should not be done on the whole of it. Instead only the nodes with odd degree should be included in the matching. Otherwise we can't argue that our minimum perfect matching is smaller than the matching on the optimal solution... — Preceding unsigned comment added by 195.176.111.6 (talk) 15:24, 7 July 2017 (UTC)Reply