On the length of optimal TSP circuits in sets of bounded diameter (Q762465): Difference between revisions

For a set V of n points in \({\mathbb{R}}^ k\), let \(\ell (V)\) denote the length of the shortest circuit which passes through all the points of V. Define \(\ell (k,n)=\max \ell (V),\) where the maximum ranges over all sets V having diameter 1. This interesting paper studies \(\ell (k,n)\). The main results are: \[ (\pi^ 2/12)^{1/4}\cdot n^{1/2}\leq \ell (2,n)\leq (\pi /2)^{1/2}\cdot n^{1/2}+O(1)\quad and\quad \] \[ c_ k\cdot n^{1-1/k}\leq \ell (k,n)\leq ((3-\sqrt{3})k/(k-1))\cdot n^{1- 1/k}+o(n^{1-1\quad /k}). \] In the last inequality \(c_ k= \limsup_{n\to \infty}\delta (k,n)n^{1/k}>0,\) where \(\delta\) (k,n) is the maximal possible value over all sets V having diameter 1 of the minimal distance between a pair of points of V.