A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Authors:
- René van BevernRBRené van Bevern
- Viktoriia A. SluginaVSViktoriia A. Slugina
- 1 November 2020
- journal article
- research article
- Published by Elsevier in Historia Mathematica
- Vol. 53, 118-127
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Ministry of Science and Higher Education of the Russian Federation
- Russian Foundation for Basic Research
This publication has 20 references indexed in Scilit:
- Efficient Algorithms for Eulerian Extension and Rural PostmanSIAM Journal on Discrete Mathematics, 2013
- A new view on Rural Postman based on Eulerian Extension and MatchingJournal of Discrete Algorithms, 2012
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related ProblemsSIAM Journal on Computing, 1999
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- The theorem on planar graphsHistoria Mathematica, 1985
- Approximation Algorithms for Some Routing ProblemsSIAM Journal on Computing, 1978
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973
- The optimum traversal of a graphOmega, 1973
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965