Separating subadditive Euclidean functionals

If we are given $n$ random points in the hypercube $[0,1{]}^d$, then the minimum length of a Traveling Salesperson Tour through the points, the minimum length of a spanning tree, and the minimum length of a matching, etc., are known to be asymptotically $\beta n^{\frac{d-1}{d}}$ a.s., where $\beta$ is an absolute constant in each case. We prove separation results for these constants. In particular, concerning the constants ${\beta }_{\mathrm{T}\mathrm{S}\mathrm{P}}^d$, ${\beta }_{\mathrm{M}\mathrm{S}\mathrm{T}}^d$, ${\beta }_{\mathrm{M}\mathrm{M}}^d$, and ${\beta }_{\mathrm{T}\mathrm{F}}^d$ from the asymptotic formulas for the minimum length TSP, spanning tree, matching, and 2-factor, respectively, we prove that ${\beta }_{\mathrm{M}\mathrm{S}\mathrm{T}}^d<{\beta }_{\mathrm{T}\mathrm{S}\mathrm{P}}^d$, $2{\beta }_{\mathrm{M}\mathrm{M}}^d<{\beta }_{\mathrm{T}\mathrm{S}\mathrm{P}}^d$, and ${\beta }_{\mathrm{T}\mathrm{F}}^d<{\beta }_{\mathrm{T}\mathrm{S}\mathrm{P}}^d$ for all $d\ge 2$. We also asymptotically separate the TSP from its linear programming relaxation in this setting. Our results have some computational relevance, showing that a certain natural class of simple algorithms cannot solve the random Euclidean TSP efficiently.