Adrian Dumitrescu 
	
Title: On a traveling salesman problem for points in the unit cube


Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$, $k \geq 2$.
  According to an old result of Bollob{\'a}s and Meir (1992), there exists a tour $x_1, x_2, \ldots, x_n$ through the
  $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq c_k$, where
  $|x-y|$ is the Euclidean distance between $x$ and $y$, and $c_k$ is an absolute constant that
  depends only on $k$ ($x_{n+1} \equiv x_1$).
  From the other direction, for every $k \geq 2$ and $n \geq 2$, there exist $n$ points in  $[0,1]^k$,
  such that their shortest tour satisfies $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} = 2^{1/k} \cdot \sqrt{k}$.
  For the plane, the best constant is $c_2=2$ and this is the only exact value known.  
  The authors showed that one can take $c_k =  9 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$
  and conjectured that the best constant is $c_k =  2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$.
  Here we significantly improve the upper bound and show that one can take
  $c_k = 3 \sqrt5 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$; this bound is constructive.
  The improvement is based on a new lemma that is a key part in bounding from above
  the weight of a minimum spanning tree of a point set.
  We also show that $c_3 \geq 2^{7/6}$, which disproves their conjecture for $k=3$.

  Connections to matching problems, power assignment problems, suitable algorithms, and other
  related problems are discussed in this context. A slightly revised version of the Bollob{\'a}s--Meir
  conjecture is proposed as a replacement.