The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio

András Sebő, Anke van Zuylen

We give a new, strongly polynomial-time algorithm and improved analysis for the metric $s-t$ path TSP. It finds a tour of cost less than 1.53 times the optimum of the subtour elimi…