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 (98)
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 ⋮ Annealed quantitative estimates for the quadratic 2D-discrete random matching problem ⋮ 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 ⋮ On concentration of the empirical measure for radial transport costs ⋮ 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 ⋮ Riesz energy, \(L^2\) discrepancy, and optimal transport of determinantal point processes on the sphere and the flat torus ⋮ A blockchain-based framework to optimize shipping container flows in the hinterland ⋮ An algorithm to approximate the optimal expected inner product of two vectors with given marginals ⋮ Random matching in 2D with exponent 2 for Gaussian densities ⋮ Asymptotics of discrete Schrödinger bridges via chaos decomposition ⋮ Some results on the optimal matching problem for the Jacobi model ⋮ Bayesian incentive compatibility via matchings ⋮ A unifying approach to distributional limits for empirical optimal transport ⋮ Limit distribution theory for smooth \(p\)-Wasserstein distances ⋮ Empirical optimal transport between different measures adapts to lower complexity ⋮ Central limit theorems for general transportation costs ⋮ Plugin estimation of smooth optimal transport maps ⋮ There is no stationary \(p\)-cyclically monotone Poisson matching in 2d ⋮ On minimum spanning trees for random Euclidean bipartite graphs ⋮ On the optimal rate for the convergence problem in mean field control ⋮ Sharp PDE estimates for random two-dimensional bipartite matching with power cost function ⋮ 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
This page was built for publication: On optimal matchings
