A sharp deviation inequality for the stochastic traveling salesman problem. (English) Zbl 0682.68058

Rhee, WanSoo T.; Talagrand, Michel

Ann. Probab. 17, No. 1, 1-8 (1989).

For n independent and uniformly distributed points in the unit square the length \(T_ n\) of a shortest hamiltonian cycle is a random variable known to be remarkably concentrated around its mean \(E(T_ n)\). Here, the existence of some number K, independent of n, is proven such that \[ P(| T_ n-E(T_ n)| >t)\leq K\quad \exp (-t^ 2/K) \] for all \(t\geq 0\). The proof is based on martingale difference sequence methods.

Reviewer: U.Zimmermann

MSC:

68Q25	Analysis of algorithms and problem complexity
90C10	Integer programming
65K05	Numerical mathematical programming methods
60G48	Generalizations of martingales

Keywords:

stochastic analysis; martingale inequalities; traveling salesman problem