Euclidean semi-matchings of random samples (Q1184341)

The linear relaxation of a minimal matching problem is investigated from a probabilistic point of view. The vertices of the graphs considered here are points chosen at random in an Euclidean space, and the edge weights are the distances between points of the space. The main result is the asymptotic behavior of the length of a minimal matching when the points of the space are independent random variables with uniform distribution on \([0,1]^ d\). This result is then extended to the more general case of distributions with compact support and absolutely continuous part.