Artículo

Foss, S.; Rolla, L.T.; Sidoravicius, V. "Greedy walk on the real line" (2015) Annals of Probability. 43(3):1399-1418
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider a self-interacting process described in terms of a singleserver system with service stations at each point of the real line. The customer arrivals are given by a Poisson point processes on the space-time half plane. The server adopts a greedy routing mechanism, traveling toward the nearest customer, and ignoring new arrivals while in transit.We study the trajectories of the server and show that its asymptotic position diverges logarithmically in time. © Institute of Mathematical Statistics, 2015.

Registro:

Documento: Artículo
Título:Greedy walk on the real line
Autor:Foss, S.; Rolla, L.T.; Sidoravicius, V.
Filiación:School Of Mathematical and Computer Sciences, Actuarial Mathematics and Statistics, Heriot-Watt University, Edinburgh, EH14 4AS, United Kingdom
Departamento De Matemática, Universidad De Buenos Aires, Ciudad Universitaria, Capital Federal, C1428Ega, Argentina
Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Rio De Janeiro, 22460-320, Brazil
Palabras clave:Greedy policy; Long-term behavior; Self-interaction; Stability
Año:2015
Volumen:43
Número:3
Página de inicio:1399
Página de fin:1418
DOI: http://dx.doi.org/10.1214/13-AOP898
Título revista:Annals of Probability
Título revista abreviado:Ann. Probab.
ISSN:00911798
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00911798_v43_n3_p1399_Foss

Referencias:

  • Altman, E., Foss, S., Polling on a space with general arrival and service time distribution (1997) Oper. Res. Lett, 20, pp. 187-194
  • Altman, E., Levy, H., Queueing in space (1994) Adv. in Appl. Probab, 26, pp. 1095-1116
  • Angel, O., Benjamini, I., Virág, B., Random walks that avoid their past convex hull (2003) Electron. Commun. Probab, 8, pp. 6-16. , (electronic)
  • Beffara, V., Friedli, S., Velenik, Y., Scaling limit of the prudent walk (2010) Electron. Commun. Probab, 15, pp. 44-58
  • Benjamini, I., Berestycki, N., Random paths with bounded local time (2010) J. Eur. Math. Soc. (JEMS), 12, pp. 819-854
  • Benjamini, I., Wilson, D.B., Excited random walk (2003) Electron. Commun. Probab, 8, pp. 86-92. , (electronic)
  • Bertsimas, D.J., Ryzin, G.V., A stochastic and dynamic vehicle routing problem in the Euclidean plane (1991) Oper. Res, 39, pp. 601-615
  • Bordenave, C., Foss, S., Last, G., On the greedy walk problem (2011) Queueing Syst, 68, pp. 333-338
  • Bousquet-Mélou, M., Families of prudent self-avoiding walks (2010) J. Combin. Theory Ser. A, 117, pp. 313-344
  • Carmona, P., Petit, F., Yor, M., Beta variables as times spent in [0,∞[ by certain perturbed Brownian motions (1998) J. Lond. Math. Soc, 58 (2), pp. 239-256
  • Chaumont, L., Doney, R.A., Pathwise uniqueness for perturbed versions of Brownian motion and reflected Brownian motion (1999) Probab. Theory Related Fields, 113, pp. 519-534
  • Coffman, E.G., Jr., Gilbert, E.N., Polling and greedy servers on a line (1987) Queueing Systems Theory Appl, 2, pp. 115-145
  • Davis, B., Weak limits of perturbed random walks and the equation Y<inf>t</inf> = B<inf>t</inf> + α sup{Y<inf>s</inf>: s ≤ t} + β inf{Y<inf>s</inf>: s ≤ t} (1996) Ann. Probab, 24, pp. 2007-2023
  • Davis, B., Brownian motion and random walk perturbed at extrema (1999) Probab. Theory Related Fields, 113, pp. 501-518
  • Foss, S., Last, G., Stability of polling systems with exhaustive service policies and state-dependent routing (1996) Ann. Appl. Probab, 6, pp. 116-137
  • Foss, S., Last, G., On the stability of greedy polling systems with general service policies (1998) Probab. Engrg. Inform. Sci, 12, pp. 49-68
  • Kroese, D.P., Schmidt, V., A continuous polling system with general service times (1992) Ann. Appl. Probab, 2, pp. 906-927
  • Kroese, D.P., Schmidt, V., Single-server queues with spatially distributed arrivals (1994) Queueing Systems Theory Appl, 17, pp. 317-345
  • Kroese, D.P., Schmidt, V., Light-traffic analysis for queues with spatially distributed arrivals (1996) Math. Oper. Res, 21, pp. 135-157
  • Kurkova, I.A., A sequential clearing process (1996) Fundam. Prikl. Mat, 2, pp. 619-624
  • Kurkova, I.A., Menshikov, M.V., Greedy algorithm, Z1 case (1997) Markov Process. Related Fields, 3, pp. 243-259
  • Lawler, G.F., Schramm, O., Werner, W., Conformal invariance of planar loop-erased random walks and uniform spanning trees (2004) Ann. Probab, 32, pp. 939-995
  • Lawler, G.F., Schramm, O., Werner, W., On the scaling limit of planar self-avoiding wal (2004) Fractal Geometry and Applications: A Jubilee of Benoît Mandelbrot, Part 2. Proc. Sympos. Pure Math, 72, pp. 339-364. , Amer. Math. Soc., Providence, RI
  • Leskelä, L., Unger, F., Stability of a spatial polling system with greedy myopic service (2012) Ann. Oper. Res, 198, pp. 165-183
  • Litvak, N., Adan, I., The travel time in carousel systems under the nearest item heuristic (2001) J. Appl. Probab, 38, pp. 45-54
  • Meester, R., Quant, C., (1999) Stability and weakly convergent approximations of queueing systems on a circle, , http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7937
  • Merkl, F., Rolles, S.W.W., Linearly edge-reinforced random walks (2006) Dynamics & Stochastics. Institute of Mathematical Statistics Lecture Notes-Monograph Series, 48, pp. 66-77. , IMS, Beachwood, OH
  • Mountford, T., Tarrès, P., An asymptotic result for Brownian polymers (2008) Ann. Inst. Henri Poincaré Probab. Stat, 44, pp. 29-46
  • Pemantle, R., A survey of random processes with reinforcement (2007) Probab. Surv, 4, pp. 1-79
  • Perman, M., Werner, W., Perturbed Brownian motions (1997) Probab. Theory Related Fields, 108, pp. 357-383
  • Raimond, O., Schapira, B., Excited Brownian motions (2011) ALEA Lat. Am. J. Probab. Math. Stat, 8, pp. 19-41
  • Robert, P., The evolution of a spatial stochastic network (2010) Stochastic Process. Appl, 120, pp. 1342-1363
  • Rojas-Nandayapa, L., Foss, S., Kroese, D.P., Stability and performance of greedy server systems (2011) A review and open problems. Queueing Syst, 68, pp. 221-227
  • Rolla, L.T., Sidoravicius, V., Stability of the greedy algorithm on the circle, , arXiv:1112.2389
  • Schassberger, R., Stability of polling networks with state-dependent server routing (1995) Probab. Engrg. Inform. Sci, 9, pp. 539-550
  • Schramm, O., Scaling limits of loop-erased random walks and uniform spanning trees (2000) Israel J. Math, 118, pp. 221-288
  • Smirnov, S., Critical percolation in the plane: Conformal invariance, Cardy's formula, scaling limits (2001) C. R. Acad. Sci. Paris Sér. I Math, 333, pp. 239-244
  • Smirnov, S., Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model (2010) Ann. of Math, 172 (2), pp. 1435-1467
  • Tóth, B., The "true" self-avoiding walk with bond repulsion on Z: Limit theorems (1995) Ann. Probab, 23, pp. 1523-1556
  • Tóth, B., Self-interacting random motions-A surve (1999) Random Walks (Budapest, 1998). Bolyai Soc. Math. Stud, 9, pp. 349-384. , János Bolyai Math. Soc., Budapest
  • Tóth, B., Werner, W., The true self-repelling motion (1998) Probab. Theory Related Fields, 111, pp. 375-452
  • Zerner, M.P.W., On the speed of a planar random walk avoiding its past convex hull (2005) Ann. Inst. Henri Poincaré Probab. Stat, 41, pp. 887-900

Citas:

---------- APA ----------
Foss, S., Rolla, L.T. & Sidoravicius, V. (2015) . Greedy walk on the real line. Annals of Probability, 43(3), 1399-1418.
http://dx.doi.org/10.1214/13-AOP898
---------- CHICAGO ----------
Foss, S., Rolla, L.T., Sidoravicius, V. "Greedy walk on the real line" . Annals of Probability 43, no. 3 (2015) : 1399-1418.
http://dx.doi.org/10.1214/13-AOP898
---------- MLA ----------
Foss, S., Rolla, L.T., Sidoravicius, V. "Greedy walk on the real line" . Annals of Probability, vol. 43, no. 3, 2015, pp. 1399-1418.
http://dx.doi.org/10.1214/13-AOP898
---------- VANCOUVER ----------
Foss, S., Rolla, L.T., Sidoravicius, V. Greedy walk on the real line. Ann. Probab. 2015;43(3):1399-1418.
http://dx.doi.org/10.1214/13-AOP898