Constant factor approximation for ATSP with two edge weights (extended abstract)

DOI10.1007/978-3-319-33461-5_19MaRDI QIDQ3186505zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Constant factor approximation for ATSP with two edge weights
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• An improved approximation algorithm for ATSP

Cites work

• \(\frac {13}{9}\)-approximation for graphic TSP
• 8/7-approximation algorithm for (1,2)-TSP
• A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
• A Randomized Rounding Approach to the Traveling Salesman Problem
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Approximating Graphic TSP by Matchings
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 1306896 (Why is no real title available?)
• New inapproximability bounds for TSP
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• 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 asymmetric traveling salesman problem on graphs with bounded genus
• The design of approximation algorithms
• The Traveling Salesman Problem with Distances One and Two

Cited in

(4)

• Constant factor approximation for ATSP with two edge weights
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem

This page was built for publication: Constant factor approximation for ATSP with two edge weights (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186505)