Jump to content

Talk:Christofides algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]