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 language | Undefined |
---|---|
Pages (from-to) | 275-280 |
Journal | Mathematics of operations research |
Volume | 14 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1989 |
Keywords
- IR-98540