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

CREATORAlessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05045

Browse the full library · About the Tower of Babel