On the Fluctuations of the Stochastic Traveling Salesperson Problem

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