Quantizers ad the worst case Euclidean traveling salesman problem (Q1111946): Difference between revisions

For \(k\geq 2\) we consider a worst-case instance of the Euclidean traveling salesman problem through n points in the unit k-cube \([0,1]^ k\). That is, for each n we arrange n points in the k-cube so that the shortest circuit containing them is as long as possible. Such optimum circuits are known to have length asymptotic to \(\alpha_ k\sqrt{k}n^{(k-1)/k}\) as \(n\to \infty\), where \(\alpha_ k\) depends only on k and is bounded. We are concerned with the problem of determining \(\alpha_ k\), for small values of k and also the asymptotic behavior of \(\alpha_ k\) as \(k\to \infty\). It was shown by \textit{L. Few} [Mathematika 2, 141-144 (1955; Zbl 0067.126)] that \(3^{-1/4}\leq \alpha_ 2\leq 1\) and that for \(k\geq 3\), \[ (\Gamma (1+k/2))^{-1/k}(\pi k)^{-1/2}\leq \alpha_ k \leq k^{1/2}(2^{-1/2}(k-1)^{-1/2})^{((k-2)/k)} \] so that, for large k, \(0.2419\lesssim \alpha_ k\lesssim 0.7071\). Later, \textit{S. Moran} [J. Comb. Theory, Ser. B 37, 113-141 (1984; Zbl 0557.52008)] improved the upper bound, for large k, to \(\alpha_ k\lesssim 0.6136\). Few's upper bound is better than Moran's for small values of k. Here, we sharpen each of these upper bounds by a factor of about \(\sqrt{2}\). By generalizing the classic ``strip'' algorithm used by Few, we obtain \[ \alpha_ k\leq k^{1/2}(2\gamma_{k-1})^{((k-1)/k)} \] where \(\gamma_ k\) is the mean deviation per dimension of the best quantizer of unit density in \({\mathbb{E}}^ k\) [for the study of quantizers see the papers in IEEE Trans. Inf. Theory IT-28, No.2 (1982), in particular \textit{P. L. Zador}, ibid., 139-149 (1982; Zbl 0476.94008)]. \(\gamma_ k\) can be roughly defined as follows: Let R be a very large k- dimensional cube with integer volume M, and let z be a uniformly distributed random point in R. Then \(\gamma_ k\) is the least possible expected value of \((1/k)\| z-Q(z)\|_ 2\), over all functions Q from R onto an M-subset of R (Q is called a quantizer for R). Numerically, we have \(\gamma_ 1=0.25\), \(\gamma_ k<0.271/\sqrt{k}\) and \(\gamma_ k\sqrt{k}\to 0.2420..\). (not monotonically) as \(k\to \infty.\) We also review Moran's asymptotic upper bound on \(\alpha_ k\). By using recent estimates on the maximum sphere packing density, we improve Moran's argument to give \(\alpha_ k\lesssim 0.4051\). Again, the latter bound is the better one only when k is large.