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
| CREATOR | Bo-Cheng Lin, Yi Mei, Mengjie Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40673 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20236