Approximating graphic TSP by b-matchings
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
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}'