Christofides algorithm - Revision history

Cedar101: /* Example */ →

2025-04-25T06:43:46Z

Example: →

← Previous revision		Revision as of 06:43, 25 April 2025
Line 64:		Line 64:
	\|[[File:TuM.svg\|200px]] \|\| Unite matching and spanning tree {{math\|''T'' ∪ ''M''}} to form an Eulerian multigraph		\|[[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->B->C->A->D->E->A. Equally valid is A->B->C->A->E->D->A.		\|[[File:Eulertour.svg\|200px]] \|\| Calculate Euler tour<br><br>Here the tour goes A→B→C→A→D→E→A. Equally valid is A→B→C→A→E→D→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->B->C->E->D->A) if this is an euclidean graph as the route A->B->C->D->E->A has intersecting lines which is proven not to be the shortest route.		\|[[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→B→C→E→D→A) if this is an euclidean graph as the route A→B→C→D→E→A has intersecting lines which is proven not to be the shortest route.
	\|}		\|}

Citation bot: Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Spanning tree | #UCB_Category 34/40

2025-01-10T07:11:13Z

Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Spanning tree | #UCB_Category 34/40

← Previous revision		Revision as of 07:11, 10 January 2025
Line 82:		Line 82:
	\| publisher = Association for Computing Machinery		\| publisher = Association for Computing Machinery
	\| title = STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021		\| title = STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
	\| year = 2021}}</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>		\| 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 <math>c>0</math>, there is a polynomial-time algorithm that finds a tour of length at most <math>1+\tfrac1c</math> times the optimal for geometric instances of TSP in		In the special case of [[Euclidean space]] of dimension <math>d</math>, for any <math>c>0</math>, there is a polynomial-time algorithm that finds a tour of length at most <math>1+\tfrac1c</math> times the optimal for geometric instances of TSP in

Altenmann at 08:36, 19 December 2024

2024-12-19T08:36:24Z

← Previous revision		Revision as of 08:36, 19 December 2024
Line 2:		Line 2:
	{{CS1 config\|mode=cs2}}		{{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>		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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}}		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 Serdyukov ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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 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=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>		</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>

David Eppstein: /* Further developments */ which one

2024-12-19T05:00:31Z

Further developments: which one

← Previous revision		Revision as of 05:00, 19 December 2024
Line 90:		Line 90:
	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.		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.

	Methods based on ~~this~~ 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		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
	\| last1 = Frederickson \| first1 = Greg N.		\| last1 = Frederickson \| first1 = Greg N.
	\| last2 = Hecht \| first2 = Matthew S.		\| last2 = Hecht \| first2 = Matthew S.

David Eppstein: /* Further developments */ clarify why

2024-12-19T04:59:59Z

Further developments: clarify why

← Previous revision		Revision as of 04:59, 19 December 2024
Line 84:		Line 84:
	\| year = 2021}}</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>		\| year = 2021}}</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]], 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		In the special case of [[Euclidean space]] of dimension <math>d</math>, for any <math>c>0</math>, there is a polynomial-time algorithm that finds a tour of length at most <math>1+\tfrac1c</math> times the optimal for geometric instances of TSP in

	:<math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right)</math> time;		:<math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right)</math> time.

	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.		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.

	Methods based on this 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		Methods based on this 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

David Eppstein: clarify

2024-12-19T03:44:14Z

clarify

← Previous revision		Revision as of 03:44, 19 December 2024
Line 2:		Line 2:
	{{CS1 config\|mode=cs2}}		{{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>		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}); the ~~latter~~ discovered it independently in 1976 (but ~~the~~ ~~publication~~ ~~is dated~~ 1978).<ref name=cri>{{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}}		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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 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=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>		</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>

David Eppstein: originally cs2; restore consistent citation style. Update Karlin et al. Add stacker crane problem.

2024-12-19T03:42:40Z

originally cs2; restore consistent citation style. Update Karlin et al. Add stacker crane problem.

@@ Line 1: / Line 1: @@
 {{Short description|Approximation for the travelling salesman problem}}
 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]] ({{langx|ru|Анатолий Иванович Сердюков}}); the latter discovered it independently in 1976 (but the publication is dated 1978).<ref name=cri>{{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}}
@@ Line 69: / Line 70: @@
 ==Further developments==
 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
@@ Line 77: / Line 89: @@
 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.
 == References ==

Monkbot: Task 20: replace {lang-??} templates with {langx|??} ‹See Tfd› (Replaced 1);

2024-11-01T00:40:53Z

Task 20: replace {lang-??} templates with {langx|??} ‹See Tfd› (Replaced 1);

← Previous revision		Revision as of 00:40, 1 November 2024
Line 1:		Line 1:
	{{Short description\|Approximation for the travelling salesman problem}}		{{Short description\|Approximation for the travelling salesman problem}}
	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>		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]] ({{~~lang-~~ru\|Анатолий Иванович Сердюков}}); the latter discovered it independently in 1976 (but the publication is dated 1978).<ref name=cri>{{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}}		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}); the latter discovered it independently in 1976 (but the publication is dated 1978).<ref name=cri>{{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 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=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>		</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>

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:54:45Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:54, 12 October 2024
Line 86:		Line 86:
	[[Category:1976 in computing]]		[[Category:1976 in computing]]
	[[Category:Travelling salesman problem]]		[[Category:Travelling salesman problem]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]
	[[Category:Approximation algorithms]]		[[Category:Approximation algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:21:59Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:21, 12 October 2024
Line 86:		Line 86:
	[[Category:1976 in computing]]		[[Category:1976 in computing]]
	[[Category:Travelling salesman problem]]		[[Category:Travelling salesman problem]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]
	[[Category:Approximation algorithms]]		[[Category:Approximation algorithms]]

← Previous revision		Revision as of 08:36, 19 December 2024
Line 2:		Line 2:
	{{CS1 config\|mode=cs2}}		{{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>		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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}}		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 Serdyukov ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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 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=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>		</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>

← Previous revision		Revision as of 03:44, 19 December 2024
Line 2:		Line 2:
	{{CS1 config\|mode=cs2}}		{{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>		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}); the ~~latter~~ discovered it independently in 1976 (but ~~the~~ ~~publication~~ ~~is dated~~ 1978).<ref name=cri>{{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}}		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]] ({{langx\|ru\|Анатолий Иванович Сердюков}}). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<ref name=cri>{{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 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=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>		</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>