Near-minimal spanning trees : a scaling exponent in probability models

David J. Aldous; Charles Bordenave; Marc Lelarge

Annales de l'I.H.P. Probabilités et statistiques (2008)

  • Volume: 44, Issue: 5, page 962-976
  • ISSN: 0246-0203

Abstract

top
We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.

How to cite

top

Aldous, David J., Bordenave, Charles, and Lelarge, Marc. "Near-minimal spanning trees : a scaling exponent in probability models." Annales de l'I.H.P. Probabilités et statistiques 44.5 (2008): 962-976. <http://eudml.org/doc/77999>.

@article{Aldous2008,
abstract = {We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.},
author = {Aldous, David J., Bordenave, Charles, Lelarge, Marc},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {combinatorial optimization; continuum percolation; disordered lattice; local weak convergence; minimal spanning tree; Poisson point process; probabilistic analysis of algorithms; random geometric graph},
language = {eng},
number = {5},
pages = {962-976},
publisher = {Gauthier-Villars},
title = {Near-minimal spanning trees : a scaling exponent in probability models},
url = {http://eudml.org/doc/77999},
volume = {44},
year = {2008},
}

TY - JOUR
AU - Aldous, David J.
AU - Bordenave, Charles
AU - Lelarge, Marc
TI - Near-minimal spanning trees : a scaling exponent in probability models
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2008
PB - Gauthier-Villars
VL - 44
IS - 5
SP - 962
EP - 976
AB - We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.
LA - eng
KW - combinatorial optimization; continuum percolation; disordered lattice; local weak convergence; minimal spanning tree; Poisson point process; probabilistic analysis of algorithms; random geometric graph
UR - http://eudml.org/doc/77999
ER -

References

top
  1. [1] D. J. Aldous and A. G. Percus. Scaling and universality in continuous length combinatorial optimization. Proc. Natl. Acad. Sci. USA 100 (2003) 11211–11215. Zbl1063.90041MR2007286
  2. [2] D. J. Aldous. The ζ(2) limit in the random assignment problem. Random Structures Algorithms 18 (2001) 381–418. Zbl0993.60018MR1839499
  3. [3] D. J. Aldous and J. M. Steele. Asymptotics for Euclidean minimal spanning trees on random points. Probab. Theory Related Fields 92 (1992) 247–258. Zbl0767.60005MR1161188
  4. [4] D. J. Aldous and J. M. Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures 1–72. H. Kesten (Ed.). Springer, Berlin, 2003. Zbl1037.60008MR2023650
  5. [5] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87–104. Zbl0827.60079MR1330762
  6. [6] K. S. Alexander. Simultaneous uniqueness of infinite clusters in stationary random labeled graphs. Comm. Math. Phys. 168 (1995) 39–55. Zbl0827.60080MR1324390
  7. [7] G. Chartrand and L. Lesniak. Graphs and Digraphs, 2nd edition. Wadsworth, Monterey, CA, 1986. Zbl0666.05001MR834583
  8. [8] L. P. Kadanoff. Statistical Physics. World Scientific, River Edge, NJ, 2000. Zbl0952.82001MR1772071
  9. [9] W. Krauth and M. Mézard. The cavity method and the travelling-salesman problem. Europhys. Lett. 8 (1989) 213–218. 
  10. [10] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, 1996. Zbl0858.60092MR1409145
  11. [11] J. M. Steele. Probability Theory and Combinatorial Optimization. SIAM, Philadelphia, PA, 1997. Zbl0916.90233MR1422018
  12. [12] M. Penrose and J. E. Yukich. Weak laws of large numbers in geometric probability. Ann. Appl. Probab. 13 (2003) 277–303. Zbl1029.60008MR1952000
  13. [13] J. E. Yukich. Probability Theory of Classical Euclidean Optimization Problems. Springer, Berlin, 1998. Zbl0902.60001MR1632875

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.