A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
From MaRDI portal
Publication:2660410
DOI10.1016/j.hm.2020.04.003zbMath1462.90114arXiv2004.02437OpenAlexW3099932027MaRDI QIDQ2660410
René van Bevern, Viktoriia A. Slugina
Publication date: 30 March 2021
Published in: Historia Mathematica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.02437
Combinatorial optimization (90C27) History of operations research and mathematical programming (90-03)
Related Items (11)
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 ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ 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 ⋮ Approximation algorithms for multi-vehicle stacker crane problems ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Approximating TSP walks in subcubic graphs ⋮ Two-machine routing open shop: How long is the optimal makespan?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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 theorem on planar graphs
- A new view on rural postman based on Eulerian extension and matching
- On Eulerian extensions and their application to no-wait flowshop scheduling
- The Travelling Salesman and the PQ-Tree
- The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
- Overview of New Approaches for Approximating TSP
- The Design of Approximation Algorithms
- From Few Components to an Eulerian Graph by Adding Arcs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- 8/7-approximation algorithm for (1,2)-TSP
- Heuristic analysis, linear programming and branch and bound
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Computational Complexity of Discrete Optimization Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Matching, Euler tours and the Chinese postman
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- The Salesman’s Improved Paths through Forests
- Approaching 3/2 for the s - t -path TSP
- Efficient Algorithms for Eulerian Extension and Rural Postman
- Fast minimum-weight double-tree shortcutting for metric TSP
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Parameterized Algorithms
- Maximum matching and a polyhedron with 0,1-vertices
- Encyclopedia of Algorithms
This page was built for publication: A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
