A sharp deviation inequality for the stochastic traveling salesman problem

DOI10.1214/AOP/1176991490zbMath0682.68058OpenAlexW1976730470MaRDI QIDQ1824393

WanSoo T. Rhee, Michel Talagrand

Publication date: 1989

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aop/1176991490

zbMATH Keywords

traveling salesman problemstochastic analysismartingale inequalities

Mathematics Subject Classification ID

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

Related Items (15)

On the fluctuations of simple matching ⋮ On properties of geometric random problems in the plane ⋮ Concentration of measure and isoperimetric inequalities in product spaces ⋮ The central limit theorem for Euclidean minimal spanning trees. I ⋮ Computing the variance of tour costs over the solution space of the TSP in polynomial time ⋮ Unnamed Item ⋮ The physicist's approach to the travelling salesman problem. II ⋮ Euclidean semi-matchings of random samples ⋮ A weak convergence result useful in robust autoregression ⋮ On the long edges in the shortest tour through \(n\) random points ⋮ Scaling and universality in continuous length combinatorial optimization ⋮ The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees ⋮ Riesz transforms for $1\le p\le 2$ ⋮ On some approximately balanced combinatorial cooperative games ⋮ Rate of convergence for the Euclidean minimum spanning tree limit law

This page was built for publication: A sharp deviation inequality for the stochastic traveling salesman problem