{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}