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 βnd−1d a.s., where β is an absolute constant in each case. We prove separation results for these constants. In particular, concerning the constants βdTSP, βdMST, βdMM, and βdTF from the asymptotic formulas for the minimum length TSP, spanning tree, matching, and 2-factor, respectively, we prove that βdMST<βdTSP, 2βdMM<βdTSP, and βdTF<βdTSP for all d≥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.