Update (2011). Nicolas Broutin points out that (i) was proved long ago. See this 1989 paper by Mike Steele for a proof and reference to an earlier proof by Bentley and Saxe (1980).

Greedy tour length and the greedy spatial service algorithm

These are two closely related questions.

Greedy tours.

Take n points i.i.d. uniform on the unit square. Starting at an arbitary point, a "server" moves successively to the closest point not previously visited. This gives a tour through all n points, with some random length L_n. It is natural to conjecture
(i) E [L_n] = O(n^{-1/2})
(ii) n^{-1/2} EL_n \to c, for some constant c.

Greedy spatial service algorithm

Consider the following model, in the class of models discussed by Bertsimas - van Ryzin (1993) and subsequent O.R. literature. Items arrive according to the times of a Poisson process of rate lambda < 1 at i.i.d. uniform positions in the unit square. Each item requires unit service time. A server, upon completing service of one item, moves at unit speed to the closest remaining item and commences service of that item. It is natural to conjecture that the long-run mean waiting time (for an arriving item to have its service completed) is O( (1 - lambda)^{-2})) as lambda \to 1. Bertsimas - van Ryzin (1993) show this is the best possible order and is attained by variant algorithms;

Problem: Prove this for the stated "greedy algorithm".

History. The service algorithm version is implicit in Bertsimas - van Ryzin (1993) who show simulation results; I mentioned it in a 1998 talk (Conference in Honor of Harry Kesten). The greedy tour problem is likely folklore from the early days of probabilistic analysis of TSP. It is mentioned in Yukich's 1998 monograph Probability theory of classical Euclidean optimization problems and was included in my 2003 postscript version of these Open Problems.