Probabilistic Behavior of Shortest Paths Over Unbounded Regions
Report ID: TR-313-91Author: Yao, Andrew
Date: 1991-03-00
Pages: 19
Download Formats: |PDF|
Abstract:
Let $k^>^1$ and $P$ be a probability distribution over $R sup k$ with all its absolute $mu$-th moments being finite for some $mu ^ > ^k/(k^-^1)$. Let $v sub 1$,$v sub 2$, $cdot cdot cdot$ be an infinite sequence of random points, each independently distributed according to $P$. It is shown that the length of the shortest traveling-salesman's tour through $v sub 1$,$v sub 2$,$cdot cdot cdot$,$v sub n$ is, for large $n$, almost surely around $alpha p n sup (k-1)/K$ for some constant $alpha p$. This proves a conjecture of Beardwood, Halton and Hammersley (Proc. Camb. Phil. Soc. 55 (1959), 299-327).