A (Slightly) Improved Approximation Algorithm for Metric TSP

2020/07/02 by Karlin, Anna R., Klein, Nathan, Gharan, Shayan Oveis · 17 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2007.01409

Abstract

For some ε> 10^-36 we give a randomized 3/2-ε approximation algorithm for metric TSP.

Cited by

• Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach
• TSP with Predictions: Heatmap to Tour with Provable Guarantees
• TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima
• Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
• Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
• Tight eigenvalue bound on the traveling salesman problem
• Reinforced Generation of Combinatorial Structures: Hardness of Approximation
• Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
• Graph Traversal via Connected Mobile Agents
• An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
• Dual Charging for Half-Integral TSP
• Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
• The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components
• Approximation and Hardness of Polychromatic TSP
• Almost Tight Additive Guarantees for k-Edge-Connectivity
• Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
• An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication

Related

• A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
• Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time
• On Approximation Lower Bounds for TSP with Bounded Metrics
• Fast Approximations for Metric-TSP via Linear Programming
• 13/9-approximation for Graphic TSP