Combinatorial Optimization Over Two Random Point Sets

Let (X, Y) be a pair of random point sets in Rd of equal cardinal obtained by sampling independently 2n points from a common probability distribution mu. In this paper, we are interested by functions L of (X,Y) which appear in combinatorial optimization. Typical examples include the minimal length of a matching of X and Y, the length of a traveling salesperson tour constrained to alternate between points of each set, or the minimal length of a connected bipartite r-regular graph with vertex set (X, Y). As the size n of the point sets goes to infinity, we give sufficient conditions on the function L and the probability measure mu which guarantee the convergence of L (X, Y) under a suitable scaling. In the case of the minimal length matching, we extend results of Dobric and Yukich, and Boutet de Monvel and Martin.