Random assignment problems on 2d manifolds
From MaRDI portal
Random assignment problems on \(2d\) manifolds
Abstract: We consider the assignment problem between two sets of random points on a smooth, two-dimensional manifold of unit area. It is known that the average cost scales as with a correction that is at most of order . In this paper, we show that, within the linearization approximation of the field-theoretical formulation of the problem, the first -dependent correction is on the constant term, and can be exactly computed from the spectrum of the Laplace--Beltrami operator on . We perform the explicit calculation of this constant for various families of surfaces, and compare our predictions with extensive numerics.
Recommendations
- On random multi-dimensional assignment problems
- Asymptotic results for random multidimensional assignment problems
- Randomized Approximation Algorithm for a Geometrical Multidimensional Assignment Problem
- Asymptotic properties of random multidimensional assignment problems
- On the optimal map in the 2-dimensional random matching problem
- Computational studies of randomized multidimensional assignment problems
- Asymptotics in the random assignment problem
- ON THE RANDOM n×n ASSIGNMENT PROBLEM
- Random assignment problems
Cites work
- scientific article; zbMATH DE number 5297651 (Why is no real title available?)
- scientific article; zbMATH DE number 3437224 (Why is no real title available?)
- scientific article; zbMATH DE number 1975241 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- 100 years of Weyl's law
- A PDE approach to a 2-dimensional matching problem
- A geometrical mass and its extremal properties for metrics on S^2
- A negative mass theorem for surfaces of positive genus
- A negative mass theorem for the 2-torus
- A note on deformations of 2D fluid motions using 3D Born-Infeld equations
- A proof of Parisi's conjecture on the random assignment problem
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- Correlation function for the grid-Poisson Euclidean matching on a line and on a circle
- Derivation of the Euler equations from a caricature of Coulomb interaction
- Distributing many points on a sphere
- Elliptic functions, Green functions and the mean field equations on tori
- Euclidean random matching in 2D for non-constant densities
- Extremals for logarithmic Hardy-Littlewood-Sobolev inequalities on compact manifolds
- Extremals of determinants of Laplacians
- Finer estimates on the 2-dimensional matching problem
- Foundations of the new field theory
- Gravitational allocation on the sphere
- Matching theory
- Minimal discrete energy on the sphere
- On optimal matchings
- On the optimal map in the 2-dimensional random matching problem
- Optimal Transport
- Optimal transportation on non-compact manifolds
- Sharp inequalities for functional integrals and traces of conformally invariant operators.
- Sum rules for zeros of Bessel functions and an application to spherical Aharonov-Bohm quantum bags
- The \(\zeta(2)\) limit in the random assignment problem
- The spectrum of positive elliptic operators and periodic bicharacteristics
Cited in
(6)- Random matching in 2D with exponent 2 for Gaussian densities
- On the quadratic random matching problem in two-dimensional domains
- Optimal transport methods for combinatorial optimization over two random point sets
- Sharp PDE estimates for random two-dimensional bipartite matching with power cost function
- Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
- Minimal matchings of point processes
This page was built for publication: Random assignment problems on \(2d\) manifolds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034668)
