Counting Locally Optimal Tours in the TSP

Bodo Manthey; Jesse van Rhijn

doi:10.48550/arXiv.2410.18650

Counting Locally Optimal Tours in the TSP

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

13 Downloads (Pure)

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 \sqrt{n!})$. Based on numerical experiments, we conjecture that the true bound is at most $O(\sqrt{n!})$, which is approximately the square root of the total number of tours.

Original language	English
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2410.18650
Publication status	Published - 24 Oct 2024

Keywords

cs.DS
cs.CC
cs.DM

Access to Document

10.48550/arXiv.2410.18650Licence: CC BY

2410.18650v1Final published version, 504 KBLicence: CC BY

Counting Locally Optimal Tours in the TSP
Manthey, B. & van Rhijn, J., 20 Aug 2025, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025. Gawrychowski, P., Mazowiecki, F. & Skrzypczak, M. (eds.). Dagstuhl: Dagstuhl, 73. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 345).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
5 Downloads (Pure)

Cite this

@techreport{7deff4013aff4fbeaeda82692170ea8c,

title = "Counting Locally Optimal Tours in the TSP",

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\textasciicircum{}n \textbackslash{}sqrt\{n!\})\$. Based on numerical experiments, we conjecture that the true bound is at most \$O(\textbackslash{}sqrt\{n!\})\$, which is approximately the square root of the total number of tours. ",

keywords = "cs.DS, cs.CC, cs.DM",

author = "Bodo Manthey and \{van Rhijn\}, Jesse",

year = "2024",

month = oct,

day = "24",

doi = "10.48550/arXiv.2410.18650",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Counting Locally Optimal Tours in the TSP

AU - Manthey, Bodo

AU - van Rhijn, Jesse

PY - 2024/10/24

Y1 - 2024/10/24

N2 - 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 \sqrt{n!})$. Based on numerical experiments, we conjecture that the true bound is at most $O(\sqrt{n!})$, which is approximately the square root of the total number of tours.

AB - 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 \sqrt{n!})$. Based on numerical experiments, we conjecture that the true bound is at most $O(\sqrt{n!})$, which is approximately the square root of the total number of tours.

KW - cs.DS

KW - cs.CC

KW - cs.DM

U2 - 10.48550/arXiv.2410.18650

DO - 10.48550/arXiv.2410.18650

M3 - Preprint

BT - Counting Locally Optimal Tours in the TSP

PB - ArXiv.org

ER -

Counting Locally Optimal Tours in the TSP

Abstract

Keywords

Access to Document

Fingerprint

Research output

Counting Locally Optimal Tours in the TSP

Cite this