Complete Convergence of Short Paths and Karp's Algorithm for the TSP

DOI10.1287/moor.6.3.374zbMath0496.90078OpenAlexW2145535767WikidataQ94767814 ScholiaQ94767814MaRDI QIDQ3960487

J. Michael Steele

Publication date: 1981

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1315&context=oid_papers

zbMATH Keywords

complete convergencetraveling salesman problemprobabilistic analysis of algorithmsjackknifeEfron-Stein inequalitysubadditive processessubadditive Euclidean functionalsKarp's algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Convergence of probability measures (60B10) Functional limit theorems; invariance principles (60F17) Algorithms in computer science (68W99)

Related Items

Martingale inequalities and the jackknife estimate of variance, On properties of geometric random problems in the plane, A differential version of the Efron-Stein inequality: Bounding the variance of a function of an infinitely divisible variable, The iterated jackknife estimate of variance, Continuous approximation models in freight distribution management, Smoothed analysis of partitioning algorithms for Euclidean functionals, An appraisal of computational complexity for operations researchers, Euclidean semi-matchings of random samples, Rates of convergence of means of Euclidean functionals, On the long edges in the shortest tour through \(n\) random points, The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees, Travelling Salesman with a Self-Similar Itinerary, Convergence of optimal stochastic bin packing