Talk:Christofides algorithm
Latest comment: 7 years ago by 195.176.111.6 in topic Approximation wrong
This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
Text and/or other creative content from Travelling salesman problem was copied or moved into Christofides algorithm. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. |
Approximation wrong
editI 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)