A constant-factor approximation algorithm for the asymmetric traveling salesman problem
From MaRDI portal
Publication:5230290
DOI10.1145/3188745.3188824zbMath1428.90146arXiv1708.04215OpenAlexW3102266534MaRDI QIDQ5230290
Jakub Tarnawski, Ola Svensson, László A. Végh
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.04215
linear programmingcombinatorial optimizationapproximation algorithmsasymmetric traveling salesman problem
Related Items (20)
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 ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Search and delivery man problems: when are depth-first paths optimal? ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ 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 for Directed Latency in Quasi-Polynomial Time ⋮ Collapsing Superstring Conjecture ⋮ The temporal explorer who returns to the base ⋮ The asymmetric traveling salesman path LP has constant integrality ratio ⋮ Thin trees in some families of distance-regular graphs ⋮ Approximation Algorithms for the Single Robot Line Coverage Problem ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
This page was built for publication: A constant-factor approximation algorithm for the asymmetric traveling salesman problem
