How Long Can a Euclidean Traveling Salesman Tour Be?

Author:
  • HKHoward J. Karloff
    Howard J. Karloff

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$.

This publication has 7 references indexed in Scilit: