Combinatorial Optimization Over Two Random Point Sets

By Franck Barthe, Charles Bordenave. 2011

82 citations recorded by the source corpus.

Let \((\mathcal{X},\mathcal{Y})\) be a pair of random point sets in \({\mathbb{R}}^{d}\) of equal cardinal obtained by sampling independently 2n points from a common probability distribution μ. In this paper, we are interested by functions L of \((\mathcal{X},\mathcal{Y})\) which appear in combinatorial optimization. Typical examples include the minimal length of a matching of \(\mathcal{X}\) and \(\mathcal{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 \((\mathcal{X},\mathcal{Y})\). As the size n of the point sets goes to infinity, we give sufficient conditions on the function L and the probability measure μ which guarantee the convergence of \(L(\mathcal{X},\mathcal{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.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/4156f8e33cf4c41ad05e02d777e72c1397b1fc3e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Constructive quantization: Approximation by empirical measures (2011, background): “Interestingly, there has been progress on this class of problems in several aspects [2,4] parallel to our research.”
On the mean speed of convergence of empirical and occupation measures in Wasserstein distance (2011, background): “…proof in [12] proves useful in our case, and the technique of using a sequence of coarser and coarser partitions is at the heart of many later results, notably in the literature concerned with the problem of matching two independent samples in Euclidean space, see e.g. [29] or the recent paper [2].”
Simple Bounds for the Convergence of Empirical and Occupation Measures in 1-Wasserstein Distance (2011, background): “Bordenave [3], one may get an estimate of the type EW1(Ln, μ) ≤ cn under some polynomial moment condition on μ.”
On Kac's chaos and related problems (2012, background): “shing rates of convergence in MKW distance in the above convergence has been addressed for instance in [28, 1, 26, 62, 55, 10], while the optimality of that rates have been considered for instance in [1, 68, 26, 4]. We refer to [4, 10] and the references therein for a recent discussion on that topic”
On Optimal Matching of Gaussian Samples (2019, background): “Furthermore, for irregular laws, the decay can be faster (see [7, 15]), but we do not address this issue here.”
Statistical Aspects of Wasserstein Distances (2018, background): “See Bass (1955) and Dall’Aglio (1956) for early references, and Cuesta-Albertos et al. (1993) for detailed discussion when p = 2.”
On the rate of convergence in Wasserstein distance of the empirical measure (2013, unknown): “…Pag`es-Wilbertz [33] for recent results), optimal matching (see Ajtai-Koml´os-Tusn´ady [2], Dobri´c-Yukich [19], Talagrand [39], Barthe-Bordenave [3]), density estimation, clustering (see Biau-Devroye-Lugosi [5] and Lalo¨e [26]), MCMC methods (see [36] for bounds on ergodic averages), particle…”