Answers are grounded in this paper and cite their sources.
We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most 89/64=7/5-3/320 times the value of the subtour relaxation. This improves the long-standing ratio 75 of Sebő and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most 89/64≈ 1.3906. We optimize a non-linear objective function over an odd-join polytope, which uses (i) a new removable system of edges, and (ii) reconnection of subtours if the graph is disconnected. This approach gives a 13/10-approximation algorithm for $4$-regular $4$-vertex-connected graphs, improving the 43 of Newman, and a 43-approximation for k-vertex-connected graphs of maximum degree at most $k+1$, for every k≥ 3. For the general graphic TSP, we construct a feasible point in the odd-join polytope, using an optimal vertex from the Subtour linear programming relaxation of TSP, which helps us bound the approximation factor by 89/64.
No takes yet. Share an insight, caveat, or question.
Gupta et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: