Premium
On the Travelling Salesperson Problem in Many Dimensions
Author(s) -
Rhee Wansoo T.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030302
Subject(s) - constant (computer programming) , combinatorics , mathematics , travelling salesman problem , discrete mathematics , computer science , algorithm , programming language
Consider d ⩾ 2, and m points X 1 , …, X m that are independent uniformly distributed in [0, 1] d . It is well known that the length T m of the shortest tour through X 1 , …, X m satisfies lim m → ∞ E ( T m )/ m 1−1/ d = β( d ) for a certain number β( d ). We show that for some numerical constant K ,\documentclass{article}\pagestyle{empty}\begin{document}$$ |\beta (d)\, - \,(d/2\pi e)^{1/2} | \le \,K(\log \,d)/d $$\end{document} .