An improved approximation algorithm for ATSP

DOI10.1145/3357713.3384233zbMath1489.68404arXiv1912.00670OpenAlexW3035464720MaRDI QIDQ5144891

Jens Vygen, Vera Traub

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

traveling salesman problemapproximation algorithmsintegrality ratio

Mathematics Subject Classification ID

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

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