A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

DOI10.1145/3424306zbMath1499.68407OpenAlexW3096239448MaRDI QIDQ5056450

Ola Svensson, Jakub Tarnawski, László A. Végh

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3424306

zbMATH Keywords

connectivitytraveling salesman problemnetwork flowsHeld-Karp relaxationsubtours

Mathematics Subject Classification ID

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

Related Items (8)

The simultaneous semi-random model for TSP ⋮ Auction algorithm sensitivity for multi-robot task allocation ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization

This page was built for publication: A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem