Combinatorial Optimization Over Two Random Point Sets

DOI10.1007/978-3-319-00321-4_19zbMath1401.90180arXiv1103.2734OpenAlexW1893250775MaRDI QIDQ2865119

Charles Bordenave, Franck Barthe

Publication date: 28 November 2013

Published in: Lecture Notes in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.2734

zbMATH Keywords

combinatorial optimizationgeometric probabilityminimal matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (24)

Rate of convergence of the Nanbu particle system for hard potentials and Maxwell molecules ⋮ On the quadratic random matching problem in two-dimensional domains ⋮ A fluctuation result for the displacement in the optimal matching problem ⋮ Parametrization of Random Vectors in Polynomial Chaos Expansions via Optimal Transportation ⋮ Constructive quantization: approximation by empirical measures ⋮ $k$-Variance: A Clustered Notion of Variance ⋮ Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures ⋮ Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds ⋮ Optimal transport methods for combinatorial optimization over two random point sets ⋮ Behavior of the empirical Wasserstein distance in \({\mathbb R}^d\) under moment conditions ⋮ On the mean speed of convergence of empirical and occupation measures in Wasserstein distance ⋮ A PDE approach to a 2-dimensional matching problem ⋮ Gravitational allocation for uniform points on the sphere ⋮ On the rate of convergence in Wasserstein distance of the empirical measure ⋮ On Kac's chaos and related problems ⋮ An algorithm to approximate the optimal expected inner product of two vectors with given marginals ⋮ Some results on the optimal matching problem for the Jacobi model ⋮ On optimal matching of Gaussian samples ⋮ On the rate of convergence of empirical measure in $\infty $-Wasserstein distance for unbounded density function ⋮ A simple Fourier analytic proof of the AKT optimal matching theorem ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ One-dimensional empirical measures, order statistics, and Kantorovich transport distances ⋮ Finer estimates on the \(2\)-dimensional matching problem ⋮ Transport inequalities on Euclidean spaces for non-Euclidean metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric properties of Poisson matchings
• Poisson matching
• On optimal matchings
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Matching random samples in many dimensions
• A matching problem and subadditive Euclidean functionals
• The integrability of the square exponential transportation cost
• Asymptotics for transportation cost in high dimensions
• Probability theory of classical Euclidean optimization problems
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Almost sure convergence of the minimum bipartite matching functional in Euclidean space
• On the Stochastic Euclidean Travelling Salesperson Problem for Distributions with Unbounded Support

This page was built for publication: Combinatorial Optimization Over Two Random Point Sets