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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Almost sure convergence of the minimum bipartite matching functional in Euclidean space
scientific article

    Statements

    Almost sure convergence of the minimum bipartite matching functional in Euclidean space (English)
    0 references
    14 October 2003
    0 references
    Let \(X_1,\dots,X_N,\dots\) and \(Y_1,\dots,Y_N,\dots\) be two sequences of random points independently and uniformly distributed in the unit cube of \(d\)-dimensional Euclidean space. Let \(L_N\) denote the minimum length of bipartite matching between \(X_1,\dots,X_N\) and \(Y_1,\dots,Y_N\). It is shown that for \(d\geq 3\), \(L_N /N^{1-1/d}\) converges almost surely to a positive constant as \(N\to\infty\).
    0 references
    almost sure convergence
    0 references
    minimum bipartite matching problem
    0 references

    Identifiers