On the minimal travel time needed to collect $n$ items on a circle

Nelli Litvak, Willem R. van Zwet

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

11 Downloads (Pure)

Abstract

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.
Original languageUndefined
Title of host publicationSelected Works of Willem van Zwet
EditorsSarah van der Geer, Marten Wegkamp
Place of PublicationNew York
PublisherSpringer
Pages371-392
Number of pages22
ISBN (Print)978-1-4614-1313-4
DOIs
Publication statusPublished - 2012

Publication series

NameSelected Works in Probability and Statistics
PublisherSpringer
ISSN (Print)1050-5164
ISSN (Electronic)2168-8737

Keywords

  • EWI-22566
  • Uniform spacings
  • IR-83428
  • METIS-289794
  • Exponential functionals
  • Exact distributions
  • Asymptotics
  • Carousel systems

Cite this

Litvak, N., & van Zwet, W. R. (2012). On the minimal travel time needed to collect $n$ items on a circle. In S. van der Geer, & M. Wegkamp (Eds.), Selected Works of Willem van Zwet (pp. 371-392). (Selected Works in Probability and Statistics). New York: Springer. https://doi.org/10.1007/978-1-4614-1314-1_22
Litvak, Nelli ; van Zwet, Willem R. / On the minimal travel time needed to collect $n$ items on a circle. Selected Works of Willem van Zwet. editor / Sarah van der Geer ; Marten Wegkamp. New York : Springer, 2012. pp. 371-392 (Selected Works in Probability and Statistics).
@inbook{1385d301917e471e869c04e52bd753b5,
title = "On the minimal travel time needed to collect $n$ items on a circle",
abstract = "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.",
keywords = "EWI-22566, Uniform spacings, IR-83428, METIS-289794, Exponential functionals, Exact distributions, Asymptotics, Carousel systems",
author = "Nelli Litvak and {van Zwet}, {Willem R.}",
note = "10.1007/978-1-4614-1314-1_22",
year = "2012",
doi = "10.1007/978-1-4614-1314-1_22",
language = "Undefined",
isbn = "978-1-4614-1313-4",
series = "Selected Works in Probability and Statistics",
publisher = "Springer",
pages = "371--392",
editor = "{van der Geer}, Sarah and Marten Wegkamp",
booktitle = "Selected Works of Willem van Zwet",

}

Litvak, N & van Zwet, WR 2012, On the minimal travel time needed to collect $n$ items on a circle. in S van der Geer & M Wegkamp (eds), Selected Works of Willem van Zwet. Selected Works in Probability and Statistics, Springer, New York, pp. 371-392. https://doi.org/10.1007/978-1-4614-1314-1_22

On the minimal travel time needed to collect $n$ items on a circle. / Litvak, Nelli; van Zwet, Willem R.

Selected Works of Willem van Zwet. ed. / Sarah van der Geer; Marten Wegkamp. New York : Springer, 2012. p. 371-392 (Selected Works in Probability and Statistics).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - On the minimal travel time needed to collect $n$ items on a circle

AU - Litvak, Nelli

AU - van Zwet, Willem R.

N1 - 10.1007/978-1-4614-1314-1_22

PY - 2012

Y1 - 2012

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

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

KW - EWI-22566

KW - Uniform spacings

KW - IR-83428

KW - METIS-289794

KW - Exponential functionals

KW - Exact distributions

KW - Asymptotics

KW - Carousel systems

U2 - 10.1007/978-1-4614-1314-1_22

DO - 10.1007/978-1-4614-1314-1_22

M3 - Chapter

SN - 978-1-4614-1313-4

T3 - Selected Works in Probability and Statistics

SP - 371

EP - 392

BT - Selected Works of Willem van Zwet

A2 - van der Geer, Sarah

A2 - Wegkamp, Marten

PB - Springer

CY - New York

ER -

Litvak N, van Zwet WR. On the minimal travel time needed to collect $n$ items on a circle. In van der Geer S, Wegkamp M, editors, Selected Works of Willem van Zwet. New York: Springer. 2012. p. 371-392. (Selected Works in Probability and Statistics). https://doi.org/10.1007/978-1-4614-1314-1_22