A (slightly) improved approximation algorithm for metric TSP

DOI10.1145/3406325.3451009arXiv2007.01409OpenAlexW3167350281MaRDI QIDQ6065169

Nathan Klein, Anna R. Karlin, Shayan Oveis Gharan

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsrandomized roundingtraveling salesperson problemstrongly Rayleighmax entropynear minimum cuts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (21)

From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ On quasisymmetric mappings in semimetric spaces ⋮ The simultaneous semi-random model for TSP ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ Auction algorithm sensitivity for multi-robot task allocation ⋮ A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Minimizing the maximum flow time in the online food delivery problem ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Approximating TSP walks in subcubic graphs ⋮ Approximation algorithms for solving the heterogeneous Chinese postman problem

This page was built for publication: A (slightly) improved approximation algorithm for metric TSP