On the rate of convergence of some stochastic processes

Walter Kern

doi:10.1287/moor.14.2.275

On the rate of convergence of some stochastic processes

Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic

104 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 language	Undefined
Pages (from-to)	275-280
Journal	Mathematics of operations research
Volume	14
Issue number	2
DOIs	https://doi.org/10.1287/moor.14.2.275
Publication status	Published - 1989

Keywords

IR-98540

Access to Document

10.1287/moor.14.2.275

3689706

Cite this

@article{5ee455ff55d049d6a836a93a69c037f2,

title = "On the rate of convergence of some stochastic processes",

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.).",

keywords = "IR-98540",

author = "Walter Kern",

year = "1989",

doi = "10.1287/moor.14.2.275",

language = "Undefined",

volume = "14",

pages = "275--280",

journal = "Mathematics of operations research",

issn = "0364-765X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "2",

}

TY - JOUR

T1 - On the rate of convergence of some stochastic processes

AU - Kern, Walter

PY - 1989

Y1 - 1989

N2 - 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.).

AB - 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.).

KW - IR-98540

U2 - 10.1287/moor.14.2.275

DO - 10.1287/moor.14.2.275

M3 - Article

VL - 14

SP - 275

EP - 280

JO - Mathematics of operations research

JF - Mathematics of operations research

SN - 0364-765X

IS - 2

ER -