The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances
Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi · 2025
Read The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances by Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05045.txt.
Description
Alessandro Sosso, Ambrogio Maria Bernardelli, and Stefano Gualandi give a new way to compute the integrality gap for small cases of the asymmetric traveling salesman problem. That gap gauges how far a relaxed math form can drift from true tour costs.
Their method lists pairs of cycle covers, then maps them to half-integer points of the relaxed polytope, skipping copies by a set order. A fast check tests if a point is truly a corner of that shape. The flip in order beats past methods that made all corners first, and it matches known results for up to nine cities.
Catalog record
| CREATOR | Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-05045