A Sharp Deviation Inequality for the Stochastic Traveling Salesman Problem

Abstract

Let $T_n$ denote the length of the shortest closed path connecting $n$ random points uniformly distributed over the unit square. We prove that for some number $K$, we have, for all $t \geq 0$, $P(|T_n - E(T_n)| \geq t) \leq K \exp(-t^2/K).$

Locations

• The Annals of Probability - View - PDF