Minimax grid matching and empirical measures

DOI10.1214/AOP/1176990347MaRDI QIDQ810990zbMATHOpenAlexFDO

Authors Peter W. Shor, J. E. Yukich

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

Convergence of probability measures (60B10) 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)

Recommendations

• Optimal Matching and Empirical Measures
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• scientific article; zbMATH DE number 434646
• Large and moderate deviations for matching problems and empirical discrepancies
• scientific article; zbMATH DE number 434648

Cited in

(25)

• Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
• The spectrum of a random geometric graph is concentrated
• A PDE approach to a 2-dimensional matching problem
• A simple Fourier analytic proof of the AKT optimal matching theorem
• Analysis of \(p\)-Laplacian regularization in semisupervised learning
• On the rate of convergence of empirical measure in \(\infty \)-Wasserstein distance for unbounded density function
• Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences
• Dilation bootstrap
• Belief propagation for MiniMax Weight Matching
• Transport inequalities on Euclidean spaces for non-Euclidean metrics
• Optimal Matching and Empirical Measures
• Correlation function for the grid-Poisson Euclidean matching on a line and on a circle
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• About the Prohorov distance between the uniform distribution over the unit cube in \(R^ d\) and its empirical measure
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• A variational approach to the consistency of spectral clustering
• Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds
• Properly-weighted graph Laplacian for semi-supervised learning
• Continuum limit of total variation on point clouds
• Monotone properties of random geometric graphs have sharp thresholds
• On optimal matching of Gaussian samples
• Kac's representation from an asymptotic viewpoint
• Optimal Cheeger cuts and bisections of random geometric graphs
• On the spectrum of dense random geometric graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810990)