Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-10T19:44:04.645Z Has data issue: false hasContentIssue false
  • English
  • Français

THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS

Published online by Cambridge University Press:  05 April 2021

David J. Aldous Open the ORCID record for David J. Aldous [Opens in a new window]
David J. Aldous*
Affiliation:
Department of Statistics, University of California, Berkeley, California 94720, USA E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We revisit an old topic in algorithms, the deterministic walk on a finite graph which always moves toward the nearest unvisited vertex until every vertex is visited. There is an elementary connection between this cover time and ball-covering (metric entropy) measures. For some familiar models of random graphs, this connection allows the order of magnitude of the cover time to be deduced from first passage percolation estimates. Establishing sharper results seems a challenging problem.

Keywords

deterministic walkmetric entropynearest neighborrandom graph
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 36 , Issue 3 , July 2022 , pp. 851 - 867
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © The Author(s), 2021. Published by Cambridge University Press

References

Aldous, D.J. (2016). Weak concentration for first passage percolation times on graphs and general increasing set-valued processes. ALEA. Latin American Journal of Probability and Mathematical Statistics 13(2): 925–940.CrossRefGoogle Scholar
Aldous, D.J. (2021). Exploring endless space. In preparation.Google Scholar
Aldous, D.J. & Steele, J.M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In H. Kesten (ed.), Probability on Discrete Structures. Encyclopaedia of Mathematical Sciences, vol. 110. Berlin: Springer, pp. 1–72.CrossRefGoogle Scholar
Auffinger, A., Damron, M., & Hanson, J. (2017). 50 years of first-passage percolation, vol. 68. Providence, RI: American Mathematical Society University Lecture Series.CrossRefGoogle Scholar
Benjamini, I. & Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electronic Journal of Probabability 6: 1–13.Google Scholar
Bordenave, C., Foss, S., & Last, G. (2011). On the greedy walk problem. Queueing Systems 68: 333–338.CrossRefGoogle Scholar
Ding, J., Lee, J.R., & Peres, Y. (2012). Cover times, blanket times, and majorizing measures. Annals of Mathematics 175(3): 1409–1471.CrossRefGoogle Scholar
Frieze, A.M. (1985). On the value of a random minimum spanning tree problem. Discrete Applied Mathematics 10(1): 47–56.CrossRefGoogle Scholar
Hirsch, C., Neuhäuser, D., Gloaguen, C., & Schmidt, V. (2015). First passage percolation on random geometric graphs and an application to shortest-path trees. Advances in Applied Probability 47(2): 328–354.CrossRefGoogle Scholar
Hougardy, S. & Wilde, M. (2015). On the nearest neighbor rule for the metric traveling salesman problem. Discrete Applied Mathematics 195: 101–103.CrossRefGoogle Scholar
Hurkens, C.A.J. & Woeginger, G.J. (2004). On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters 32(1): 1–4.CrossRefGoogle Scholar
Janson, S. (1999). One, two and three times log n/n for paths in a complete graph with random weights. Combinatorics, Probabability and Computing 8(4): 347–361.CrossRefGoogle Scholar
Johnson, D.S. & Papadimitriou, C.H. (1985). Performance guarantees for heuristics. In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, & D. B. Shmoys (eds), The traveling salesman problem. Wiley-Interscience Series in Discrete Mathematics. Chichester: Wiley, pp. 145–180.Google Scholar
Kesten, H. (1986). Aspects of first passage percolation. In École d’été de probabilités de Saint-Flour, XIV—1984, vol. 1180. Lecture Notes in Mathematics. Berlin: Springer, pp. 125–264.CrossRefGoogle Scholar
Kesten, H. & Lee, S. (1996). The central limit theorem for weighted minimal spanning trees on random points. Annals of Applied Probability 6(2): 495–527.CrossRefGoogle Scholar
Megow, N., Mehlhorn, K., & Schweitzer, P. (2012). Online graph exploration: New results on old and new algorithms. Theoretical Computer Science 463: 62–72.CrossRefGoogle Scholar
Mézard, M. & Parisi, G. (1986). A replica analysis of the travelling salesman problem. Journal de Physique 47: 1285–1296.CrossRefGoogle Scholar
Pinsky, M.A. & Karlin, S (2011). An introduction to stochastic modeling. Amsterdam: Elsevier/Academic Press.Google Scholar
Rosenkrantz, D.J., Stearns, R.E., & Lewis II, P.M. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing 6(3): 563–581.CrossRefGoogle Scholar
Steele, J.M. (1989). Cost of sequential connection for points in space. Operations Research Letters 8(3): 137–142.CrossRefGoogle Scholar
Steele, J.M (1997). Probability theory and combinatorial optimization. In CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 69. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM).CrossRefGoogle Scholar
Wästlund, J. (2010). The mean field traveling salesman and related problems. Acta Mathematica 204(1): 91–150.CrossRefGoogle Scholar
Yukich, J.E. (1998). Probability theory of classical Euclidean optimization problems, vol. 1675. Lecture Notes in Mathematics. Berlin: Springer-Verlag.CrossRefGoogle Scholar