On the rate of convergence of some stochastic processes

Walter Kern

Research output: Contribution to journalArticleAcademic

104 Downloads (Pure)


We present a general technique for obtaining bounds on the deviation of the optimal value of some stochastic combinatorial problems from their mean. As a particular application, we prove an exponential rate of convergence for the length of a shortest path through n random points in the unit square. This strengthens a previous result of Steele (Steele, J.M. 1981. Complete convergence of short paths and Karp's algorithm for the TPS. Math.Oper.Res.).
Original languageUndefined
Pages (from-to)275-280
JournalMathematics of operations research
Issue number2
Publication statusPublished - 1989


  • IR-98540

Cite this