On optimal matchings
From MaRDI portal
Publication:1056968
DOI10.1007/BF02579135zbMath0562.60012OpenAlexW1981557399MaRDI QIDQ1056968
János Komlós, Gábor Tusnády, Miklós Ajtai
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579135
Geometric probability and stochastic geometry (60D05) Stopping times; optimal stopping problems; gambling theory (60G40)
Related Items
A Poisson allocation of optimal tail, On the quadratic random matching problem in two-dimensional domains, Poisson matching, Constructions of majorizing measures, Bernoulli processes and cotype, A fluctuation result for the displacement in the optimal matching problem, Convergence of asymptotic costs for random Euclidean matching problems, Asymptotics for transportation cost in high dimensions, Scaling and non-standard matching theorems, Limit laws of the empirical Wasserstein distance: Gaussian distributions, Random complex zeroes. II. Perturbed lattice, The average-case analysis of some on-line algorithms for bin packing, On the Euclidean assignment problem, Unnamed Item, Optimal transport from Lebesgue to Poisson, Generalized moments of the distance between Poisson process events, Convergence rates for empirical measures of Markov chains in dual and Wasserstein distances, Euclidean random matching in 2D for non-constant densities, Constructive quantization: approximation by empirical measures, The empirical cost of optimal incomplete transportation, Optimal Matching and Empirical Measures, Optimal random matchings, tours, and spanning trees in hierarchically separated trees, Random restricted matching and lower bounds for combinatorial optimization, There is no stationary cyclically monotone Poisson matching in 2d, Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, Continuous approximation formulas for location problems, Density estimation of multivariate samples using Wasserstein distance, Correlation length of the two-dimensional random field Ising model via greedy lattice animal, The Convergence Problem in Mean Field Games with Neumann Boundary Conditions, Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric, The Wasserstein distance to the circular law, Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds, Donsker theorems for occupation measures of multi-dimensional periodic diffusions, Asymptotics for Strassen's optimal transport problem, Optimal transport methods for combinatorial optimization over two random point sets, Applications of No-Collision Transportation Maps in Manifold Learning, Inference for Empirical Wasserstein Distances on Finite Spaces, Rates of convergence for partial mass problems, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, Behavior of the empirical Wasserstein distance in \({\mathbb R}^d\) under moment conditions, Empirical measures: regularity is a counter-curse to dimensionality, Asymptotic analysis of the optimal cost in some transportation problems with random locations, On the mean speed of convergence of empirical and occupation measures in Wasserstein distance, On the event distance of Poisson processes with applications to sensors, A PDE approach to a 2-dimensional matching problem, Anomalous scaling of the optimal cost in the one-dimensional random assignment problem, Gravitational allocation for uniform points on the sphere, On the Wasserstein distance between classical sequences and the Lebesgue measure, Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle, On the rate of convergence in Wasserstein distance of the empirical measure, Rényi 100, quantitative and qualitative (in)dependence, Coalescence on the real line, Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures, Approximation algorithms for the Euclidean bipartite TSP, Properly-weighted graph Laplacian for semi-supervised learning, Rate of convergence of bootstrapped empirical measures, Gravitational allocation to Poisson points, Random assignment problems on \(2d\) manifolds, Empirical optimal transport on countable metric spaces: distributional limits and statistical applications, 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, Bayesian incentive compatibility via matchings, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, A variational approach to regularity theory in optimal transportation, Filling random cycles, On optimal matching of Gaussian samples, A Wasserstein inequality and minimal Green energy on compact manifolds, 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, Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences, 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, Bin Packing with Queues, Matchings and the variance of Lipschitz functions, Minimal matchings of point processes, Combinatorial Optimization Over Two Random Point Sets, Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus, The Dyck bound in the concave 1-dimensional random assignment model, On optimal matching of Gaussian samples III, Continuum limit of total variation on point clouds
Cites Work
