Optimal transport methods for combinatorial optimization over two random point sets

DOI10.1007/s00440-023-01245-1arXiv2209.14615MaRDI QIDQ6193775

Dario Trevisan, Michael Goldman

Publication date: 19 March 2024

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

matching problemoptimal transportgeometric probabilitytravelling salesperson problem

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Linear programming (90C05) Combinatorial optimization (90C27) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Functional inequalities, including subadditivity, convexity, etc. (39B62) (L^p)-limit theorems (60F25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructive quantization: approximation by empirical measures
• On optimal matchings
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Matching random samples in many dimensions
• The Euclidean traveling salesman problem is NP-complete
• Asymptotics for transportation cost in high dimensions
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Almost sure convergence of the minimum bipartite matching functional in Euclidean space
• A PDE approach to a 2-dimensional matching problem
• Bounds of Riesz transforms on \(L^p\) spaces for second order elliptic operators.
• The inhomogeneous Dirichlet problem in Lipschitz domains
• Asymptotics for the Euclidean TSP with power weighted edges
• Random assignment problems on \(2d\) manifolds
• A simple Fourier analytic proof of the AKT optimal matching theorem
• Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus
• Asymptotics of smoothed Wasserstein distances
• On the quadratic random matching problem in two-dimensional domains
• A fluctuation result for the displacement in the optimal matching problem
• Finer estimates on the \(2\)-dimensional matching problem
• On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
• Concentration of the hypergeometric distribution
• Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups
• Euclidean random matching in 2D for non-constant densities
• Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds
• Combinatorial Optimization Over Two Random Point Sets
• Random Measures, Theory and Applications
• Algorithms for the Assignment and Transportation Problems
• Quantitative Linearization Results for the <scp>Monge‐Ampère</scp> Equation
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Gradient estimate on convex domains and applications
• Gravitational allocation on the sphere
• On optimal matching of Gaussian samples III
• Moser-Trudinger inequalities without boundary conditions and isoperimetric problems
• Lectures on the Poisson Process
• Comparison between W₂ distance and Ḣ⁻¹ norm, and Localization of Wasserstein distance
• The Speed of Mean Glivenko-Cantelli Convergence

This page was built for publication: Optimal transport methods for combinatorial optimization over two random point sets