Minimax grid matching and empirical measures

DOI10.1214/aop/1176990347zbMath0734.60005OpenAlexW1976755703MaRDI QIDQ810990

Joseph E. Yukich, Peter W. Shor

Publication date: 1991

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aop/1176990347

zbMATH Keywords

empirical measuresProkhorov distanceminimax grid matching problem

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Convergence of probability measures (60B10)

Related Items (23)

Kac's representation from an asymptotic viewpoint ⋮ The spectrum of a random geometric graph is concentrated ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ On the spectrum of dense random geometric graphs ⋮ Optimal Matching and Empirical Measures ⋮ Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds ⋮ Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures ⋮ Belief Propagation for MiniMax Weight Matching ⋮ Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator ⋮ Dilation bootstrap ⋮ A PDE approach to a 2-dimensional matching problem ⋮ Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle ⋮ Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures ⋮ Monotone properties of random geometric graphs have sharp thresholds ⋮ Properly-weighted graph Laplacian for semi-supervised learning ⋮ A variational approach to the consistency of spectral clustering ⋮ On optimal matching of Gaussian samples ⋮ Analysis of $p$-Laplacian Regularization in Semisupervised Learning ⋮ 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 ⋮ Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences ⋮ Transport inequalities on Euclidean spaces for non-Euclidean metrics ⋮ Continuum limit of total variation on point clouds

This page was built for publication: Minimax grid matching and empirical measures