Constant factor approximation for ATSP with two edge weights

DOI10.1007/S10107-017-1195-7zbMATH Open1411.90301arXiv1511.07038OpenAlexW3136659659MaRDI QIDQ1801010FDOQ1801010

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)

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.

Full work available at URL: https://arxiv.org/abs/1511.07038

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

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)

Cites Work

• 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
• The Traveling Salesman Problem with Distances One and Two
• 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
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• \(\frac {13}{9}\)-approximation for graphic TSP
• New inapproximability bounds for TSP
• Title not available (Why is that?)
• A generalization of permanent inequalities and applications in counting and optimization
• The asymmetric traveling salesman problem on graphs with bounded genus
• Title not available (Why is that?)
• A near-optimal approximation algorithm for asymmetric TSP on embedded graphs

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
• Constant factor approximation for ATSP with two edge weights (extended abstract)
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• 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)