How Long Can a Euclidean Traveling Salesman Tour Be?
Author:
- Howard J. KarloffHKHoward J. Karloff
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 2 (1) , 91-99
Abstract
Where S is a set of N points in the unit square, let $t(S)$ be the Euclidean length of the shortest traveling salesman tour through S. Let $t_N = \max_st (S)$. We improve Few’s bound [Mathematika, 2 (1955), pp. 141–144] that $t_N \leqq \sqrt {2N} + 7/4$ to $t_N \leqq \alpha \sqrt N + 11$, where $\alpha /\sqrt 2 < 0.984$.
Keywords
This publication has 7 references indexed in Scilit:
- Two probabilistic results on rectilinear Steiner trees1986
- On the length of optimal TSP circuits in sets of bounded diameterJournal of Combinatorial Theory, Series B, 1984
- The Travelling Salesman Problem and Minimum Matching in the Unit SquareSIAM Journal on Computing, 1983
- On Steiner trees for bounded point setsGeometriae Dedicata, 1981
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959
- The shortest path and the shortest road through n pointsMathematika, 1955
- On the shortest path through a number of pointsProceedings of the American Mathematical Society, 1951