Almost sure convergence of the minimum bipartite matching functional in Euclidean space

被引：12

作者：

De Monvel, JHB ^{[1
]}

Martin, OC

机构：

[1] Karolinska Inst, Ctr Hearing & Commun Res, S-17176 Stockholm, Sweden

[2] Univ Paris 11, Lab Phys Theor & Modeles Stat, F-91405 Orsay, France

来源：

COMBINATORICA | 2002年 / 22卷 / 04期

关键词：

D O I：

10.1007/s00493-002-0004-x

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let L-N = L-MBM (X-1,...,X-N; Y-1,...,Y-N) be the minimum length of a bipartite matching between two sets of points in R-d, where X-1,...,X-N,... and Y-1,...,Y-N,... are random points independently and uniformly distributed in [0, 1](d). We prove that for d greater than or equal to 3, L-N/N1-1/d converges with probability one to a constant beta(MBM)(d) > 0 as N --> infinity.

引用

页码：523 / 530

页数：8

共 14 条

[1] ON OPTIMAL MATCHINGS [J].

AJTAI, M ;

KOMLOS, J ;

TUSNADY, G .

COMBINATORICA, 1984, 4 (04) :259-264

[2] The ζ(2) limit in the random assignment problem [J].

Aldous, DJ .

RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (04) :381-418

[3]

[Anonymous], P CAMB PHILO SOC, DOI DOI 10.1017/S0305004100034095

[4]

Azuma K., 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286

[5] AN ASYMPTOTIC DETERMINATION OF THE MINIMUM SPANNING TREE AND MINIMUM MATCHING CONSTANTS IN GEOMETRICAL-PROBABILITY [J].

BERTSIMAS, DJ ;

VANRYZIN, G .

OPERATIONS RESEARCH LETTERS, 1990, 9 (04) :223-231

[6] Mean field and corrections for the Euclidean minimum matching problem [J].

deMonvel, JHB ;

Martin, OC .

PHYSICAL REVIEW LETTERS, 1997, 79 (01) :167-170

[7] Comparing mean field and Euclidean matching problems [J].

Houdayer, J ;

de Monvel, JHB ;

Martin, OC .

EUROPEAN PHYSICAL JOURNAL B, 1998, 6 (03) :383-393

[8] ON THE SOLUTION OF THE RANDOM LINK MATCHING PROBLEMS [J].

MEZARD, M ;

PARISI, G .

JOURNAL DE PHYSIQUE, 1987, 48 (09) :1451-1459

[9] LIMIT THEOREMS AND RATES OF CONVERGENCE FOR EUCLIDEAN FUNCTIONALS [J].

Redmond, C. ;

Yukch, J. E. .

ANNALS OF APPLIED PROBABILITY, 1994, 4 (04) :1057-1073

[10]

Rhee W.T., 1993, ANN APPL PROBAB, P794

← 1 2 →