Separating subadditive Euclidean functionals

Original · EN

If we are given n random points in the hypercube [0,1]ᵈ, 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 βnᵈ⁻¹/ᵈ a.s., where β is an absolute constant in each case. We prove separation results for these constants. In particular, concerning the constants βTSPᵈ, βMSTᵈ, βMMᵈ, and βTFᵈ from the asymptotic formulas for the minimum length TSP, spanning tree, matching, and 2-factor, respectively, we prove that βMSTᵈ<βTSPᵈ, 2βMMᵈ<βTSPᵈ, and βTFᵈ<βTSPᵈ 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.