Near-minimal spanning trees : a scaling exponent in probability models
Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008) no. 5, pp. 962-976.

Nous étudions la relation entre l’arbre couvrant minimal (ACM) sur des points aléatoires et l’arbre «quasi» optimal sous la contrainte qu’une proportion δ de ses arêtes soit différente de celles de l’ACM. Un raisonnement heuristique suggère que quelque soit le modèle probabiliste sous-jacent, le ratio des longueurs des deux arbres doit varier en 1+Θ(δ 2 ). Nous montrons ce résultat d'échelle pour le modèle de la grille avec des longueurs d'arêtes aléatoires et pour le modèle euclidien.

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.

DOI : 10.1214/07-AIHP138
Classification : 05C80, 60K35, 68W40
Mots-clés : combinatorial optimization, continuum percolation, disordered lattice, local weak convergence, minimal spanning tree, Poisson point process, probabilistic analysis of algorithms, random geometric graph 
@article{AIHPB_2008__44_5_962_0,
     author = {Aldous, David J. and Bordenave, Charles and Lelarge, Marc},
     title = {Near-minimal spanning trees : a scaling exponent in probability models},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {962--976},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {5},
     year = {2008},
     doi = {10.1214/07-AIHP138},
     mrnumber = {2453778},
     zbl = {1186.05108},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/07-AIHP138/}
}
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
SP  - 962
EP  - 976
VL  - 44
IS  - 5
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/07-AIHP138/
DO  - 10.1214/07-AIHP138
LA  - en
ID  - AIHPB_2008__44_5_962_0
ER  - 
%0 Journal Article
%A Aldous, David J.
%A Bordenave, Charles
%A Lelarge, Marc
%T Near-minimal spanning trees : a scaling exponent in probability models
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2008
%P 962-976
%V 44
%N 5
%I Gauthier-Villars
%U http://archive.numdam.org/articles/10.1214/07-AIHP138/
%R 10.1214/07-AIHP138
%G en
%F AIHPB_2008__44_5_962_0
Aldous, David J.; Bordenave, Charles; Lelarge, Marc. Near-minimal spanning trees : a scaling exponent in probability models. Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008) no. 5, pp. 962-976. doi : 10.1214/07-AIHP138. http://archive.numdam.org/articles/10.1214/07-AIHP138/

[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. | MR | Zbl

[2] D. J. Aldous. The ζ(2) limit in the random assignment problem. Random Structures Algorithms 18 (2001) 381-418. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[5] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87-104. | MR | Zbl

[6] K. S. Alexander. Simultaneous uniqueness of infinite clusters in stationary random labeled graphs. Comm. Math. Phys. 168 (1995) 39-55. | MR | Zbl

[7] G. Chartrand and L. Lesniak. Graphs and Digraphs, 2nd edition. Wadsworth, Monterey, CA, 1986. | MR | Zbl

[8] L. P. Kadanoff. Statistical Physics. World Scientific, River Edge, NJ, 2000. | MR | Zbl

[9] W. Krauth and M. Mézard. The cavity method and the travelling-salesman problem. Europhys. Lett. 8 (1989) 213-218.

[10] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, 1996. | MR | Zbl

[11] J. M. Steele. Probability Theory and Combinatorial Optimization. SIAM, Philadelphia, PA, 1997. | MR | Zbl

[12] M. Penrose and J. E. Yukich. Weak laws of large numbers in geometric probability. Ann. Appl. Probab. 13 (2003) 277-303. | MR | Zbl

[13] J. E. Yukich. Probability Theory of Classical Euclidean Optimization Problems. Springer, Berlin, 1998. | MR | Zbl

Cité par Sources :