pith. sign in

arxiv: math/0205140 · v1 · submitted 2002-05-13 · 🧮 math.CO · math.OC· math.PR

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

classification 🧮 math.CO math.OCmath.PR
keywords bipartitematchingminimumpointsalmostbetaconstantconvergence
0
0 comments X
read the original abstract

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 $\mathbf{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 \ge 3$, $L_N/N^{1-1/d}$ converges with probability one to a constant $\beta_{MBM}(d)>0$ as $N\to \infty $.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.