Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

Bo-Cheng Lin, Yi Mei, Mengjie Zhang · 2026

Read Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem by Bo-Cheng Lin, Yi Mei, Mengjie Zhang (2026) 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-2604-20236.txt.

Description

Lin, Mei, and Zhang tackle candidate graph thinning for the travelling salesman problem, where strong solvers like LKH search small pre-picked sets. The two best thinning rules clash on density versus recall: alpha-Nearest stays dense with steady recall, while POPMUSIC runs sparser but loses recall as size grows. Their union closes the recall gap near six times the node count, tagging each edge by its source. A light classifier then drops the weakest edges, keeping at least 99.69 percent of optimal tour edges while cutting density 37 to 47 percent.

Catalog record

CREATORBo-Cheng Lin, Yi Mei, Mengjie Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40673
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20236

Browse the full library · About the Tower of Babel