Extending Exact Integrality Gap Computations for the Metric TSP
The subtour relaxation of the traveling salesman problem (TSP) plays a central role in approximation algorithms and polyhedral studies of the TSP. A long-standing conjecture asserts that the integrality gap of the subtour relaxation for the metric TSP is exactly $4/3$. In this paper, we extend the exact verification of this conjecture to a larger number of vertices. Using the framework introduced by Benoit and Boyd in 2008, we confirm their results up to $n=10$. We further show that for $n=11$ and $n=12$, the published lists of extreme points of the subtour polytope are incomplete: one…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.12995
curl -X POST /api/v1/records/arxiv/2603.12995/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.12995/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'