A deterministic better-than-3/2 approximation algorithm for metric TSP

DOI10.1007/978-3-031-32726-1_19zbMath1528.90220arXiv2212.06296OpenAlexW4377200004MaRDI QIDQ6086006

Shayan Oveis Gharan, Nathan Klein, Anna R. Karlin

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• New inapproximability bounds for TSP
• Survivable networks, linear programming relaxations and the parsimonious property
• Matroid-based TSP rounding for half-integral solutions
• Shorter tours and longer detours: uniform covers and a bit beyond
• Matching, Euler tours and the Chinese postman
• Reducing path TSP to TSP
• An improved approximation algorithm for TSP in the half integral case
• On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• The Traveling-Salesman Problem and Minimum Spanning Trees
• A (slightly) improved approximation algorithm for metric TSP