An improved approximation algorithm for ATSP

DOI10.1145/3357713.3384233MaRDI QIDQ5144891zbMATH OpenOpenAlexFDO

Authors Vera Traub, Jens Vygen

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsintegrality ratiotraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V'egh. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from $506$ to $22+epsilon$ for any $epsilon>0$. This also improves the upper bound on the integrality ratio from $319$ to $22$.

Recommendations

• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• scientific article; zbMATH DE number 2086388
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• An improved approximation algorithm for the maximum TSP
• A computational evaluation of online ATSP algorithms
• Algorithms and Data Structures
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Improved deterministic approximation algorithms for max TSP
• Improved approximation algorithms for metric MaxTSP

Cited in

(25)

• Lower tolerance-based branch and bound algorithms for the ATSP
• Constant factor approximation for ATSP with two edge weights
• A constant-factor approximation for directed latency in quasi-polynomial time
• Minimizing the makespan on a single machine subject to modular setups
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• Constant factor approximation for ATSP with two edge weights (extended abstract)
• Approximation algorithms for the single robot line coverage problem
• scientific article; zbMATH DE number 1953192 (Why is no real title available?)
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Auction algorithm sensitivity for multi-robot task allocation
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
• The single robot line coverage problem: Theory, algorithms, and experiments
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• Exact exponential algorithms for clustering problems
• On the integrality gap of small asymmetric traveling salesman problems: a polyhedral and computational approach
• Some properties of the alternating separation (AS) and ASAP algorithm

This page was built for publication: An improved approximation algorithm for ATSP

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