On the greedy walk problem

Charles Bordenave (1) , Sergey Foss (2, 3) , Günter Last (4)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 School of Mathematics and Computer Sciences
3 Institute of Mathematics
4 Institut für Stochastik

This note introduces a greedy walk on Poisson and Binomial processes, which is a close relative to the well-known greedy server model. Some open problems are presented.

Mots clés: Greedy algorithm; Travelling salesperson problem; Point processes; 60G55; 60K37

Domaines: Réseaux et télécommunications [cs.NI]

Charles Bordenave, Sergey Foss, Günter Last. On the greedy walk problem. Queueing Systems, 2011, 68 (3-4), pp.333-338. ⟨10.1007/s11134-011-9246-x⟩. ⟨hal-00842014⟩