A Sharp Deviation Inequality for the Stochastic Traveling Salesman Problem
Rhee, WanSoo T. ; Talagrand, Michel
Ann. Probab., Tome 17 (1989) no. 4, p. 1-8 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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).$
Publié le : 1989-01-14
Classification:  Martingale inequalities,  shortest path,  exponential tail,  stochastic model,  68C25,  90C10,  65K05,  60G48 
@article{1176991490,
     author = {Rhee, WanSoo T. and Talagrand, Michel},
     title = {A Sharp Deviation Inequality for the Stochastic Traveling Salesman Problem},
     journal = {Ann. Probab.},
     volume = {17},
     number = {4},
     year = {1989},
     pages = { 1-8},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176991490}
}

Rhee, WanSoo T.; Talagrand, Michel. A Sharp Deviation Inequality for the Stochastic Traveling Salesman Problem. Ann. Probab., Tome 17 (1989) no. 4, pp.  1-8. http://gdmltest.u-ga.fr/item/1176991490/