New Approximation Algorithms for (1,2)-TSP
From MaRDI portal
Publication:5002675
DOI10.4230/LIPIcs.ICALP.2018.9zbMath1499.68394OpenAlexW2885246356MaRDI QIDQ5002675
Matthias Mnich, Anna Adamaszek, Katarzyna E. Paluch
Publication date: 28 July 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.9
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (4)
Approximations for the Steiner multicycle problem ⋮ Geometric Network Creation Games ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP
Cites Work
- Unnamed Item
- 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
- An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
- On the approximation hardness of dense TSP and other path problems
- Maximum ATSP with weights zero and one via half-edges
- Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
- Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
- Approximating maximum weight cycle covers in directed graphs with weights zero and one
- New Inapproximability Bounds for TSP
- On the Integrality Gap of the Subtour LP for the 1,2-TSP
- Approximation hardness of graphic TSP on cubic graphs
- 8/7-approximation algorithm for (1,2)-TSP
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
- The Traveling Salesman Problem with Distances One and Two
- Reducibility among Combinatorial Problems
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Fundamentals of Computation Theory
- Fundamentals of Computation Theory
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: New Approximation Algorithms for (1,2)-TSP
