A sharp deviation inequality for the stochastic traveling salesman problem
From MaRDI portal
Publication:1824393
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
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Generalizations of martingales (60G48)
Related Items
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
