On the rate of convergence of some stochastic processes

Walter Kern

Research output: Contribution to journalArticleAcademic

69 Downloads (Pure)

Abstract

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
Volume14
Issue number2
DOIs
Publication statusPublished - 1989

Keywords

  • IR-98540

Cite this