Constant Factor Approximation for ATSP with Two Edge Weights

DOI10.1007/978-3-319-33461-5_19zbMath1419.90098OpenAlexW2288125683MaRDI QIDQ3186505

Ola Svensson, Jakub Tarnawski, László A. Végh

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-33461-5_19

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• New inapproximability bounds for TSP
• The Design of Approximation Algorithms
• 8/7-approximation algorithm for (1,2)-TSP
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs
• The Traveling Salesman Problem with Distances One and Two
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings

This page was built for publication: Constant Factor Approximation for ATSP with Two Edge Weights