Christofides algorithm: Difference between revisions

Revision as of 19:23, 24 April 2023

Revision as of 18:15, 22 May 2023

Line 1:

The '''Christofides algorithm''' or '''Christofides–Serdyukov algorithm''' is an [[algorithm]] for finding approximate solutions to the [[travelling salesman problem]], on instances where the distances form a [[metric space]] (they are symmetric and obey the [[triangle inequality]]).<ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|pages=513–514|chapter=18.1.2 The Christofides Approximation Algorithm}}.</ref>

It is an [[approximation algorithm]] that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after [[Nicos Christofides]] and [[Anatoliy I. Serdyukov]], who discovered it independently in 1976.<ref>{{citation|last=Christofides|first=Nicos|author-link=Nicos Christofides|year=1976|title=Worst-case analysis of a new heuristic for the travelling salesman problem|others=Report 388|institution=Graduate School of Industrial Administration, CMU|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|archive-url=https://web.archive.org/web/20190721172134/https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|url-status=live|archive-date=July 21, 2019}}</ref><ref>{{citation|last1=van Bevern|first1=René|last2=Slugina|first2=Viktoriia A.|year=2020|title=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem|journal=Historia Mathematica|volume=53|pages=118–127|doi=10.1016/j.hm.2020.04.003|arxiv=2004.02437|s2cid=214803097}}</ref><ref>{{citation|last=Serdyukov|first=Anatoliy I.|date=1978|title=О некоторых экстремальных обходах в графах|trans-title = On some extremal walks in graphs|language=ru|url=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf|journal=Upravlyaemye Sistemy|volume=17|pages=76–79}}</ref> This algorithm still stands as the best polynomial time approximation algorithm that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces.

This algorithm still stands as the best polynomial time approximation algorithm that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 however, Karlin, Klein, and Gharan released a preprint in which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5&nbsp;&minus;&nbsp;10⁻³⁶. Their method follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree.<ref>{{cite arXiv|last1=Karlin|first1=Anna R.|author1-link=Anna Karlin|last2=Klein|first2=Nathan|last3=Gharan|first3=Shayan Oveis|date=2020-08-30|title=A (Slightly) Improved Approximation Algorithm for Metric TSP|class=cs.DS|eprint=2007.01409}}</ref><ref>{{Cite web|last=Klarreich|first=Erica|author-link=Erica Klarreich|title=Computer Scientists Break Traveling Salesperson Record|url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/|access-date=2020-10-10|website=Quanta Magazine|date=8 October 2020|language=en}}</ref> The paper was published at [[Symposium on Theory of Computing|STOC'21]]<ref>{{Citation |last=Karlin |first=Anna R. |title=A (slightly) improved approximation algorithm for metric TSP |date=2021-06-15 |url=https://doi.org/10.1145/3406325.3451009 |work=Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |pages=32–45 |place=New York, NY, USA |publisher=Association for Computing Machinery |doi=10.1145/3406325.3451009 |isbn=978-1-4503-8053-9 |access-date=2022-04-20 |last2=Klein |first2=Nathan |last3=Gharan |first3=Shayan Oveis|arxiv=2007.01409 }}</ref> where it received a best paper award.<ref>{{Cite web |title=ACM SIGACT - STOC Best Paper Award |url=https://www.sigact.org/prizes/best_paper.html |access-date=2022-04-20 |website=www.sigact.org}}</ref>

== Algorithm ==