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

CREATORYong Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE308 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19608

Browse the full library · About the Tower of Babel