On the Fluctuations of the Stochastic Traveling Salesperson Problem

Consider n points X₁, …, X_n independently and uniformly distributed on the unit square [0, 1]². Denote by T_n the length of the shortest tour through X₁, …, X_n. We prove that for some universal constant K, we have P(|T_n − E(T_n)| ≥ t) ≥ K⁻¹ exp(−t²K) whenever t ≤ K⁻¹n^1/2.