An improved approximation algorithm for ATSP
From MaRDI portal
Publication:5144891
DOI10.1145/3357713.3384233zbMath1489.68404arXiv1912.00670OpenAlexW3035464720MaRDI QIDQ5144891
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
Related Items (13)
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 ⋮ Auction algorithm sensitivity for multi-robot task allocation ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ 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 ⋮ 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 ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Approximation Algorithms for the Single Robot Line Coverage Problem
This page was built for publication: An improved approximation algorithm for ATSP