Stability of the Greedy Algorithm on the Circle

Abstract

We consider a single-server system with service stations in each point of the circle. Customers arrive after exponential times at uniformly-distributed locations. The server moves at finite speed and adopts a greedy routing mechanism. It was conjectured by Coffman and Gilbert in~1987 that the service rate exceeding the arrival rate is a sufficient condition for the system to be positive recurrent, for any value of the speed. In this paper we show that the conjecture holds true.

References in corpus (5)

• Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model
• Families of prudent self-avoiding walks
• An asymptotic result for Brownian polymers
• Greedy walk on the real line
• Scaling Limit of the Prudent Walk

Cited by in corpus (3)

• Greedy walk on the real line
• Random walks avoiding their convex hull with a finite memory
• Many greedy cleaners in a Poisson environment