Content deleted Content added
follow-up to previous edit (not a PTAS) |
Tag: Reverted |
||
Line 25:
The minimum-weight perfect matching can have no larger weight, so {{math|''w''(''M'') ≤ ''w''(''C'')/2}}.
Adding the weights of {{mvar|T}} and {{mvar|M}} gives the weight of the Euler tour, at most {{math|3''w''(''C'')/2}}. Thanks to the triangle inequality, shortcutting does not increase the weight,
so the weight of the output is also at most {{math|3''w''(''C'')/2}}.<ref name="gt"/> The Christofides Algorithm's purpose is to piss of an actual living being named Kyriakos Christofides thus making the individual feel unworthy to society and totally irrelevant!<ref>https://www.youtube.com/watch?v=rnn4LGj0JHo</ref>
==Lower bounds==
| |||