Constant factor approximation for ATSP with two edge weights

DOI10.1007/S10107-017-1195-7MaRDI QIDQ1801010zbMATH OpenOpenAlexFDO

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

Publication date 26 October 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.07038, http://eprints.lse.ac.uk/85331/1/V%C3%A9gh_Constant%20factor%20approximation_2017.pdf

zbMATH Keywords

asymmetric traveling salesman problemflow decomposition theoremunit edge weights

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest.

Recommendations

• Constant factor approximation for ATSP with two edge weights (extended abstract)
• 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

• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 1306896 (Why is no real title available?)
• 8/7-approximation algorithm for (1,2)-TSP
• A Randomized Rounding Approach to the Traveling Salesman Problem
• A generalization of permanent inequalities and applications in counting and optimization
• A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
• 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
• 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 Traveling Salesman Problem with Distances One and Two
• The asymmetric traveling salesman problem on graphs with bounded genus
• The design of approximation algorithms
• \(\frac {13}{9}\)-approximation for graphic TSP

Cited in

(5)

• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• Constant factor approximation for ATSP with two edge weights (extended abstract)
• The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem

This page was built for publication: Constant factor approximation for ATSP with two edge weights

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