Id: arxiv/2611.13585 Url: https://arxiv.org/abs/2611.13585 Tags: cs.DS, cs.DM, math.CO, math.OC Score: 0 Title: Approximating graphic TSP by b-matchings Domain: cs.DS Source: arxiv Authors: Swati Gupta, Mehrdad Sohrabi, Levent Tunçel Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-10 Page: https://delphi.science/r/arxiv/2611.13585 We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most $\frac{89}{64}=\frac{7}{5}-\frac{3}{320}$ times the value of the subtour relaxation. This improves the long-standing ratio $\frac75$ of Sebő and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most $\frac{89}{64}\approx 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 $\frac{13}{10}$-approximation…