Content deleted Content added
m Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms Tag: Reverted |
Undid revision 1300833131 by 2405:201:A004:F162:2582:7572:245C:4BFD (talk) |
||
| (11 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Approximation for the travelling salesman problem}}
{{CS1 config|mode=cs2}}
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
</ref><ref name=vabe>{{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 name=ser>{{citation|last=Serdyukov|first=Anatoliy|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>
Line 27 ⟶ 28:
To prove this, let {{mvar|C}} be the optimal traveling salesman tour. Removing an edge from {{mvar|C}} produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that {{math|''w''(''T'') ≤ ''w''(''C'')}} - lower bound to the cost of the optimal solution.
The algorithm addresses the problem that {{math|T}} is not a tour by identifying all the odd degree vertices in {{math|T}}; since the sum of degrees in any graph is even (by the [[
Next, number the vertices of {{mvar|O}} in cyclic order around {{mvar|C}}, and partition {{mvar|C}} into two sets of paths: the ones in which the first path vertex in cyclic order has an odd number and the ones in which the first path vertex has an even number.
Line 63 ⟶ 64:
|[[File:TuM.svg|200px]] || Unite matching and spanning tree {{math|''T'' ∪ ''M''}} to form an Eulerian multigraph
|-
|[[File:Eulertour.svg|200px]] || Calculate Euler tour<br><br>Here the tour goes A
|-
|[[File:Eulertour bereinigt.svg|200px]] || Remove repeated vertices, giving the algorithm's output.<br><br>If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A
|}
==Further developments==
This algorithm is no longer the best polynomial time approximation algorithm for the TSP on general metric spaces. Karlin, Klein, and Gharan introduced a [[randomized algorithm|randomized]] approximation algorithm with approximation ratio 1.5 − 10<sup>−36</sup>. It 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>{{citation
| last1 = Karlin | first1 = Anna R. | author1-link = Anna Karlin
| last2 = Klein | first2 = Nathan
| last3 = Gharan | first3 = Shayan Oveis
| editor1-last = Khuller | editor1-first = Samir
| editor2-last = Vassilevska Williams | editor2-first = Virginia |editor2-link = Virginia Vassilevska Williams
| arxiv = 2007.01409
| contribution = A (slightly) improved approximation algorithm for metric TSP
| doi = 10.1145/3406325.3451009
| pages = 32–45
| publisher = Association for Computing Machinery
| title = STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
| year = 2021| isbn = 978-1-4503-8053-9 }}</ref><ref>{{citation|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|magazine=Quanta Magazine|date=8 October 2020|language=en}}</ref> The paper received a best paper award at the 2021 [[Symposium on Theory of Computing]].<ref>{{citation |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>
In the special case of [[Euclidean space]] of dimension <math>d</math>, for any
▲In the special case of [[Euclidean space]], for any ''c'' > 0, where ''d'' is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/''c'') times the optimal for geometric instances of TSP in
For each constant <math>c</math> this time bound is in [[polynomial time]], so this is called a [[polynomial-time approximation scheme]] (PTAS).<ref>Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref> [[Sanjeev Arora]] and [[Joseph S. B. Mitchell]] were awarded the [[Gödel Prize]] in 2010 for their simultaneous discovery of a PTAS for the Euclidean TSP.▼
▲:<math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right)</math> time;
Methods based on the Christofides–Serdyukov algorithm can also be used to approximate the [[stacker crane problem]], a generalization of the TSP in which the input consists of ordered pairs of points from a metric space that must be traversed consecutively and in order. For this problem, it achieves an approximation ratio of 9/5.<ref>{{citation
▲this is called a [[polynomial-time approximation scheme]] (PTAS).<ref>Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref> [[Sanjeev Arora]] and [[Joseph S. B. Mitchell]] were awarded the [[Gödel Prize]] in 2010 for their simultaneous discovery of a PTAS for the Euclidean TSP.
| last1 = Frederickson | first1 = Greg N.
| last2 = Hecht | first2 = Matthew S.
| last3 = Kim | first3 = Chul E.
| doi = 10.1137/0207017
| issue = 2
| journal = [[SIAM Journal on Computing]]
| mr = 489787
| pages = 178–193
| title = Approximation algorithms for some routing problems
| volume = 7
| year = 1978}}</ref>
== References ==
Line 86 ⟶ 111:
[[Category:1976 in computing]]
[[Category:Travelling salesman problem]]
[[Category:
[[Category:Spanning tree]]
[[Category:Approximation algorithms]]
| |||