Counting Locally Optimal Tours in the TSP

2024/10/24 by Bodo Manthey, Manthey, Bodo, Jesse van Rhijn +1
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2410.18650

openalex publication_date 2024/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098ⁿ √(n!)). Based on numerical experiments, we conjecture that the true bound is at most O(√(n!)), which is approximately the square root of the total number of tours.

Related

• Balanced TSP partitioning
• An improved approximation guarantee for Prize-Collecting TSP
• A Better-Than-1.6-Approximation for Prize-Collecting TSP
• A time- and space-optimal algorithm for the many-visits TSP
• Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions