Delphi.science

Approximating graphic TSP by b-matchings

Source: arxiv.org/abs/2611.13585

Swati Gupta, Mehrdad Sohrabi, Levent Tunçel

arXivarxiv/2611.13585Nov 10, 2026cs.DSscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.13585
curl -X POST /api/v1/records/arxiv/2611.13585/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13585/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'