The frequency K i K_{i} s for symmetric traveling salesman problem
Yong Wang · 2025
Read The frequency K i K_{i} s for symmetric traveling salesman problem by Yong Wang (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-2504-19608.txt.
Introduction
The traveling salesman problem asks for the shortest tour through a set of cities, and its best tour has hidden structure. Studying complete graphs, Yong Wang counts how often each edge appears among the best short paths with fixed endpoints, a measure he calls the frequency of that edge at each path length. Edges in the best tour appear far more often than ordinary edges, and each tour edge's frequency peaks at a predictable path length near half the number of cities.
For ordinary edges, the chance of appearing falls as paths lengthen, and Wang pins down where that fall becomes certain. From these patterns he builds a dynamic programming method that finds the best tour, and tests on sample problems confirm the predicted behavior.
Catalog record
| CREATOR | Yong Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 308 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19608