2004/05/01 by Nelly Litvak, Willem R. van Zwet, W. R. van Zwet · 2 citations
Computer Science · Mathematics · #Optimization and Search Problems #Point processes and geometric inequalities #Stochastic processes and statistical mechanics #math.PR #msc:60F05 #msc:60G51. #msc:62E15 #msc:90B05
paper · pdf · doi:10.1214/105051604000000152
published as Annals of Applied Probability 2004, Vol. 14, No. 2, 881-902
openalex publication_date 2004/05/01 · arxiv created 2004/05/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Consider n items located randomly on a circle of length 1. The locations of the items are assumed to be independent and uniformly distributed on [0,1). A picker starts at point 0 and has to collect all n items by moving along the circle at unit speed in either direction. In this paper we study the minimal travel time of the picker. We obtain upper bounds and analyze the exact travel time distribution. Further, we derive closed-form limiting results when n tends to infinity. We determine the behavior of the limiting distribution in a positive neighborhood of zero. The limiting random variable is closely related to exponential functionals associated with a Poisson process. These functionals occur in many areas and have been intensively studied in recent literature.