An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem
Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li · 2025
Read An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem by Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li (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-2501-13767.txt.
Description
Mingzhao Wang and a team of co-authors solve the traveling salesman problem with a diffusion model that guesses whole tours at once. Their work appeared in twenty twenty-five. Step-by-step solvers are slow; parallel ones are fast but sloppy, and tours suffer.
Their system, DEITSP, denoises many candidate tours simultaneously in a single step, steadied by a self-consistency trick. A dual graph transformer reads both city points and the roads between them, with fewer layers for speed. Iterations alternate adding and removing noise, widening the search beyond earlier diffusion attempts. A noise schedule refines the solution space as it goes. On real and large synthetic instances, the solver matched or beat rival neural methods on quality, speed, and generalization.
Catalog record
| CREATOR | Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13767