605:
673:
726:
617:
711:
654:
635:
689:
746:
This algorithm still stands as the best polynomial time approximation algorithm for the stated problem that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 Karlin, Klein, and Gharan released a preprint in
734:
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.
423:
that matches the two endpoints of each path, and the weight of this matching is at most equal to the weight of the paths. In fact, each path endpoint will be connected to another endpoint, which also has an odd number of visits due to the nature of the tour.
418:
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. Each set of paths corresponds to a perfect matching of
866:
751:
and 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. The paper was published at
478:. Thanks to the triangle inequality, even though the Euler tour might revisit vertices, shortcutting does not increase the weight, so the weight of the output is also at most
343:
298:
498:
There exist inputs to the travelling salesman problem that cause the
Christofides algorithm to find a solution whose approximation ratio is arbitrarily close to
969:
van Bevern, René; Slugina, Viktoriia A. (2020), "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem",
1155:
1204:
Sanjeev Arora, Polynomial-time
Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
1237:
873:
747:
which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5 − 10. Theirs is a
781:
541:, and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately
1252:
1056:
771:
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/
949:
1100:
753:
435:, and thanks to the triangle inequality its corresponding matching has weight that is also at most half the weight of
256:
Steps 5 and 6 do not necessarily yield only a single result; as such, the heuristic can give several different paths.
32:
47:
that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after
1075:; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "A (Slightly) Improved Approximation Algorithm for Metric TSP".
1232:
719:
Here the tour goes A->B->C->A->D->E->A. Equally valid is A->B->C->A->E->D->A.
1242:
551:
The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately
44:
365:
produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that
52:
1247:
881:
623:
531:
175:
157:
748:
303:
910:
503:
399:), there is an even number of such vertices. The algorithm finds a minimum-weight perfect matching
245:
40:
1133:
1076:
996:
978:
936:
48:
604:
264:
The worst-case complexity of the algorithm is dominated by the perfect matching step, which has
1151:
1052:
1044:
396:
345:
complexity, because the author was only aware of a less efficient perfect matching algorithm.
267:
183:
1143:
1017:
988:
914:
234:
201:
194:
56:
514:, together with a set of edges connecting vertices two steps apart in the path with weight
1096:
760:
940:
885:
91:
63:); the latter discovered it independently in 1976 (but the publication is dated 1978).
1217:
672:
534:
in this subgraph. Then the minimum spanning tree will be given by the path, of length
1226:
1000:
877:
725:
36:
1181:
1072:
616:
224:
149:
992:
1147:
28:
1132:, New York, NY, USA: Association for Computing Machinery, pp. 32–45,
1130:
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of
Computing
1125:
942:
Worst-case analysis of a new heuristic for the travelling salesman problem
888:
in 2010 for their simultaneous discovery of a PTAS for the
Euclidean TSP.
1168:
710:
610:
Given: complete graph whose edge weights obey the triangle inequality
530:
All remaining edges of the complete graph have distances given by the
439:. The minimum-weight perfect matching can have no larger weight, so
1138:
1124:
Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2021-06-15),
1081:
983:
653:
570:
edges incident to the endpoints of the path, and has total weight
948:, Report 388, Graduate School of Industrial Administration, CMU,
861:{\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}
106:. According to the triangle inequality, for every three vertices
634:
1126:"A (slightly) improved approximation algorithm for metric TSP"
688:
361:
be the optimal traveling salesman tour. Removing an edge from
353:
The cost of the solution produced by the algorithm is within
391:
is not a tour by identifying all the odd degree vertices in
86:
be an instance of the travelling salesman problem. That is,
917:(2015), "18.1.2 The Christofides Approximation Algorithm",
559:. However, the optimal solution uses the edges of weight
1101:"Computer Scientists Break Traveling Salesperson Record"
731:
Remove repeated vertices, giving the algorithm's output.
431:, one of the two sets has at most half of the weight of
395:; since the sum of degrees in any graph is even (by the
775:) times the optimal for geometric instances of TSP in
784:
427:
Since these two sets of paths partition the edges of
306:
270:
384:- lower bound to the cost of the optimal solution.
102:assigns a nonnegative real weight to every edge of
860:
337:
292:
592:. Hence we obtain an approximation ratio of 3/2.
16:Approximation for the travelling salesman problem
244:Make the circuit found in previous step into a
8:
1018:"О некоторых экстремальных обходах в графах"
678:Construct a minimum-weight perfect matching
510:vertices, with the path edges having weight
502:. One such class of inputs are formed by a
466:gives the weight of the Euler tour, at most
1020:[On some extremal walks in graphs]
1026:Upravlyaemye Sistemy (Управляемые системы)
35:, on instances where the distances form a
1137:
1080:
982:
839:
825:
812:
783:
387:The algorithm addresses the problem that
317:
305:
281:
269:
31:for finding approximate solutions to the
599:
897:
148:Then the algorithm can be described in
1218:NIST Christofides Algorithm Definition
964:
962:
756:where it received a best paper award.
300:complexity. Serdyukov's paper claimed
1051:, Springer-Verlag, pp. 517–519,
1011:
1009:
931:
929:
230:in which each vertex has even degree.
7:
1182:"ACM SIGACT - STOC Best Paper Award"
905:
903:
901:
874:polynomial-time approximation scheme
527:chosen close to zero but positive.
357:of the optimum. To prove this, let
955:from the original on July 21, 2019
14:
919:Algorithm Design and Applications
694:Unite matching and spanning tree
39:(they are symmetric and obey the
724:
709:
687:
671:
652:
633:
615:
603:
174:be the set of vertices with odd
25:Christofides–Serdyukov algorithm
704:to form an Eulerian multigraph
248:by skipping repeated vertices (
190:has an even number of vertices.
836:
832:
819:
813:
809:
796:
640:Calculate the set of vertices
338:{\displaystyle O(n^{3}\log n)}
332:
310:
287:
274:
98:of vertices, and the function
1:
406:Next, number the vertices of
118:, it should be the case that
1016:Serdyukov, Anatoliy (1978),
1238:Travelling salesman problem
1049:Encyclopedia of Algorithms}
1047:, in Kao, Ming-Yang (ed.),
663:using only the vertices of
403:among the odd-degree ones.
33:travelling salesman problem
1269:
61:Анатолий Иванович Сердюков
921:, Wiley, pp. 513–514
566:together with two weight-
60:
1253:Approximation algorithms
993:10.1016/j.hm.2020.04.003
458:. Adding the weights of
293:{\displaystyle O(n^{3})}
260:Computational complexity
1148:10.1145/3406325.3451009
1043:Bläser, Markus (2008),
759:In the special case of
410:in cyclic order around
45:approximation algorithm
862:
339:
294:
193:Find a minimum-weight
21:Christofides algorithm
882:Joseph S. B. Mitchell
863:
659:Form the subgraph of
624:minimum spanning tree
340:
295:
215:Combine the edges of
158:minimum spanning tree
53:Anatoliy I. Serdyukov
971:Historia Mathematica
911:Goodrich, Michael T.
782:
749:randomized algorithm
742:Further developments
716:Calculate Euler tour
586:for small values of
304:
268:
223:to form a connected
937:Christofides, Nicos
644:with odd degree in
349:Approximation ratio
246:Hamiltonian circuit
41:triangle inequality
1099:(8 October 2020).
858:
335:
290:
49:Nicos Christofides
1233:1976 in computing
1157:978-1-4503-8053-9
915:Tamassia, Roberto
884:were awarded the
872:this is called a
830:
739:
738:
682:in this subgraph
397:Handshaking lemma
184:handshaking lemma
1260:
1243:Graph algorithms
1205:
1202:
1196:
1195:
1193:
1192:
1178:
1172:
1166:
1165:
1164:
1141:
1121:
1115:
1114:
1112:
1111:
1097:Klarreich, Erica
1093:
1087:
1086:
1084:
1069:
1063:
1061:
1040:
1034:
1033:
1023:
1013:
1004:
1003:
986:
966:
957:
956:
954:
947:
933:
924:
922:
907:
867:
865:
864:
859:
857:
853:
852:
851:
850:
849:
831:
826:
728:
713:
703:
691:
681:
675:
666:
662:
656:
647:
643:
637:
628:
619:
607:
600:
591:
585:
581:
569:
565:
558:
547:
540:
526:
520:
513:
509:
501:
489:
477:
465:
461:
457:
438:
434:
430:
422:
417:
414:, and partition
413:
409:
402:
394:
390:
383:
364:
360:
356:
344:
342:
341:
336:
322:
321:
299:
297:
296:
291:
286:
285:
240:
235:Eulerian circuit
229:
222:
218:
211:
207:
200:in the subgraph
199:
195:perfect matching
189:
181:
173:
166:
162:
144:
117:
113:
109:
105:
101:
97:
89:
85:
62:
1268:
1267:
1263:
1262:
1261:
1259:
1258:
1257:
1223:
1222:
1214:
1209:
1208:
1203:
1199:
1190:
1188:
1180:
1179:
1175:
1162:
1160:
1158:
1123:
1122:
1118:
1109:
1107:
1105:Quanta Magazine
1095:
1094:
1090:
1073:Karlin, Anna R.
1071:
1070:
1066:
1059:
1042:
1041:
1037:
1021:
1015:
1014:
1007:
968:
967:
960:
952:
945:
935:
934:
927:
909:
908:
899:
894:
835:
808:
792:
788:
780:
779:
761:Euclidean space
744:
733:
732:
718:
717:
695:
679:
664:
660:
645:
641:
626:
598:
587:
583:
571:
567:
560:
552:
542:
535:
522:
515:
511:
507:
499:
496:
479:
467:
463:
459:
440:
436:
432:
428:
420:
415:
411:
407:
400:
392:
388:
366:
362:
358:
354:
351:
313:
302:
301:
277:
266:
265:
262:
238:
227:
220:
216:
209:
205:
197:
187:
179:
171:
164:
160:
119:
115:
111:
107:
103:
99:
95:
87:
72:
69:
17:
12:
11:
5:
1266:
1264:
1256:
1255:
1250:
1245:
1240:
1235:
1225:
1224:
1221:
1220:
1213:
1212:External links
1210:
1207:
1206:
1197:
1186:www.sigact.org
1173:
1156:
1116:
1088:
1064:
1057:
1035:
1028:(in Russian),
1005:
958:
925:
896:
895:
893:
890:
870:
869:
856:
848:
845:
842:
838:
834:
829:
824:
821:
818:
815:
811:
807:
804:
801:
798:
795:
791:
787:
767:> 0, where
743:
740:
737:
736:
729:
721:
720:
714:
706:
705:
692:
684:
683:
676:
668:
667:
657:
649:
648:
638:
630:
629:
620:
612:
611:
608:
597:
594:
580:− 2) + 2
532:shortest paths
495:
492:
350:
347:
334:
331:
328:
325:
320:
316:
312:
309:
289:
284:
280:
276:
273:
261:
258:
254:
253:
242:
231:
213:
191:
168:
92:complete graph
68:
65:
15:
13:
10:
9:
6:
4:
3:
2:
1265:
1254:
1251:
1249:
1248:Spanning tree
1246:
1244:
1241:
1239:
1236:
1234:
1231:
1230:
1228:
1219:
1216:
1215:
1211:
1201:
1198:
1187:
1183:
1177:
1174:
1170:
1159:
1153:
1149:
1145:
1140:
1135:
1131:
1127:
1120:
1117:
1106:
1102:
1098:
1092:
1089:
1083:
1078:
1074:
1068:
1065:
1060:
1058:9780387307701
1054:
1050:
1046:
1039:
1036:
1031:
1027:
1019:
1012:
1010:
1006:
1002:
998:
994:
990:
985:
980:
976:
972:
965:
963:
959:
951:
944:
943:
938:
932:
930:
926:
920:
916:
912:
906:
904:
902:
898:
891:
889:
887:
883:
879:
878:Sanjeev Arora
875:
854:
846:
843:
840:
827:
822:
816:
805:
802:
799:
793:
789:
785:
778:
777:
776:
774:
770:
766:
762:
757:
755:
750:
741:
730:
727:
723:
722:
715:
712:
708:
707:
702:
698:
693:
690:
686:
685:
677:
674:
670:
669:
658:
655:
651:
650:
639:
636:
632:
631:
625:
621:
618:
614:
613:
609:
606:
602:
601:
595:
593:
590:
579:
575:
564:
556:
549:
545:
538:
533:
528:
525:
521:for a number
519:
505:
493:
491:
487:
483:
475:
471:
455:
451:
447:
443:
425:
404:
398:
385:
381:
377:
373:
369:
348:
346:
329:
326:
323:
318:
314:
307:
282:
278:
271:
259:
257:
251:
247:
243:
236:
232:
226:
214:
203:
196:
192:
185:
177:
169:
159:
155:
154:
153:
151:
146:
142:
138:
134:
130:
126:
122:
93:
83:
79:
75:
66:
64:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
1200:
1189:. Retrieved
1185:
1176:
1169:2023 version
1161:, retrieved
1129:
1119:
1108:. Retrieved
1104:
1091:
1067:
1048:
1045:"Metric TSP"
1038:
1029:
1025:
974:
970:
941:
918:
871:
772:
768:
764:
758:
745:
700:
696:
588:
577:
573:
562:
554:
550:
543:
536:
529:
523:
517:
497:
494:Lower bounds
485:
481:
473:
469:
453:
449:
445:
441:
426:
405:
386:
379:
375:
371:
367:
352:
263:
255:
250:shortcutting
249:
152:as follows.
147:
140:
136:
132:
128:
124:
120:
81:
77:
73:
70:
43:). It is an
37:metric space
24:
20:
18:
977:: 118–127,
886:Gödel Prize
582:, close to
94:on the set
1227:Categories
1191:2022-04-20
1163:2022-04-20
1139:2007.01409
1110:2020-10-10
1082:2007.01409
984:2004.02437
892:References
763:, for any
622:Calculate
225:multigraph
150:pseudocode
1001:214803097
844:−
803:
539:− 1
327:
182:. By the
156:Create a
67:Algorithm
29:algorithm
950:archived
939:(1976),
876:(PTAS).
699:∪
233:Form an
1032:: 76–79
754:STOC'21
596:Example
202:induced
57:Russian
1154:
1055:
999:
176:degree
114:, and
27:is an
1134:arXiv
1077:arXiv
1022:(PDF)
997:S2CID
979:arXiv
953:(PDF)
946:(PDF)
868:time;
572:(1 +
90:is a
1152:ISBN
1053:ISBN
880:and
561:1 +
516:1 +
504:path
462:and
448:) ≤
374:) ≤
219:and
170:Let
135:) ≥
127:) +
71:Let
51:and
19:The
1144:doi
989:doi
800:log
506:of
500:3/2
488:)/2
476:)/2
456:)/2
355:3/2
324:log
237:in
208:by
204:in
178:in
163:of
76:= (
23:or
1229::
1184:.
1150:,
1142:,
1128:,
1103:.
1030:17
1024:,
1008:^
995:,
987:,
975:53
973:,
961:^
928:^
913:;
900:^
576:)(
557:/2
548:.
546:/2
490:.
252:).
186:,
145:.
141:ux
133:vx
125:uv
110:,
59::
1194:.
1171:)
1167:(
1146::
1136::
1113:.
1085:.
1079::
1062:.
991::
981::
923:.
855:)
847:1
841:d
837:)
833:)
828:d
823:c
820:(
817:O
814:(
810:)
806:n
797:(
794:n
790:(
786:O
773:c
769:d
765:c
701:M
697:T
680:M
665:O
661:G
646:T
642:O
627:T
589:ε
584:n
578:n
574:ε
568:1
563:ε
555:n
553:3
544:n
537:n
524:ε
518:ε
512:1
508:n
486:C
484:(
482:w
480:3
474:C
472:(
470:w
468:3
464:M
460:T
454:C
452:(
450:w
446:M
444:(
442:w
437:C
433:C
429:C
421:O
416:C
412:C
408:O
401:M
393:T
389:T
382:)
380:C
378:(
376:w
372:T
370:(
368:w
363:C
359:C
333:)
330:n
319:3
315:n
311:(
308:O
288:)
283:3
279:n
275:(
272:O
241:.
239:H
228:H
221:T
217:M
212:.
210:O
206:G
198:M
188:O
180:T
172:O
167:.
165:G
161:T
143:)
139:(
137:w
131:(
129:w
123:(
121:w
116:x
112:v
108:u
104:G
100:w
96:V
88:G
84:)
82:w
80:,
78:V
74:G
55:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
