A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
From MaRDI portal
Publication:2660410
Abstract: One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as "the Christofides algorithm". Recently, some authors started calling it "Christofides-Serdyukov algorithm", pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukov's findings and a translation of his article from Russian into English.
Recommendations
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- A 3/4 differential approximation algorithm for traveling salesman problem
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- On the approximability of the traveling salesman problem (extended abstract)
- scientific article; zbMATH DE number 4095236
- On the approximability of the traveling salesman problem
- The approximation ratio of the greedy algorithm for the metric traveling salesman problem
- On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP
- A (slightly) improved approximation algorithm for metric TSP
- Approximate algorithms for the traveling salesman problem. II
Cites work
- 8/7-approximation algorithm for (1,2)-TSP
- A new view on rural postman based on Eulerian extension and matching
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Approaching 3/2 for the \(s\)-\(t\)-path TSP
- Computational Complexity of Discrete Optimization Problems
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Efficient algorithms for Eulerian extension and rural Postman
- Encyclopedia of algorithms. In 3 volumes
- Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
- From few components to an Eulerian graph by adding ARCS
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Heuristic analysis, linear programming and branch and bound
- scientific article; zbMATH DE number 3646634 (Why is no real title available?)
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- scientific article; zbMATH DE number 3564899 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2064412 (Why is no real title available?)
- scientific article; zbMATH DE number 2064415 (Why is no real title available?)
- Matching, Euler tours and the Chinese postman
- Maximum matching and a polyhedron with 0,1-vertices
- On Eulerian extensions and their application to no-wait flowshop scheduling
- Overview of new approaches for approximating TSP
- Parameterized algorithms
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Rural postman parameterized by the number of components of required edges
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- The design of approximation algorithms
- The salesman's improved paths through forests
- The theorem on planar graphs
- The traveling salesman problem. A computational study.
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- The travelling salesman and the PQ-tree.
Cited in
(15)- Approximating TSP walks in subcubic graphs
- Two-machine routing open shop: How long is the optimal makespan?
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints
- Approximation algorithms for some min-max postmen cover problems
- The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
- Reinforcement learning for combinatorial optimization: a survey
- Approximation algorithms for multi-vehicle stacker crane problems
- SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Ailsa H. Land and her 1979 study of the traveling salesman problem: personal reminiscences and historical remarks
- An improved approximation guarantee for prize-collecting TSP
- A better-than-1.6-approximation for prize-collecting TSP
- A better-than-1.6-approximation for prize-collecting TSP
This page was built for publication: A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2660410)
