An improved approximation algorithm for TSP in the half integral case

DOI10.1145/3357713.3384273OpenAlexW3035071390MaRDI QIDQ5144894

Anna R. Karlin, Shayan Oveis Gharan, Nathan Klein

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/1908.00227

zbMATH Keywords

traveling salesman problemapproximation algorithmsrandomized roundingcactus representationstrongly Rayleighmax entropy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (14)

Matroid-based TSP rounding for half-integral solutions ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ 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 ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Set-to-Sequence Methods in Machine Learning: A Review ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Travelling on graphs with small highway dimension ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

This page was built for publication: An improved approximation algorithm for TSP in the half integral case