Combinatorial Optimization Over Two Random Point Sets
From MaRDI portal
Abstract: We analyze combinatorial optimization problems over a pair of random point sets of equal cardinal. Typical examples include the matching of minimal length, the traveling salesperson tour constrained to alternate between points of each set, or the connected bipartite r-regular graph of minimal length. As the cardinal of the sets goes to infinity, we investigate the convergence of such bipartite functionals.
Recommendations
- Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
- Random optimization on random sets
- Combinatorial and experimental results for randomized point matching algorithms
- Randomized algorithms for the separation of point sets and for solving quadratic programs
- On Two-Point Configurations in a Random Set
- scientific article; zbMATH DE number 780783
- A Randomized Algorithm to Optimize Over Certain Convex Sets
- scientific article; zbMATH DE number 2169759
- scientific article; zbMATH DE number 2077129
Cites work
- A matching problem and subadditive Euclidean functionals
- Almost sure convergence of the minimum bipartite matching functional in Euclidean space
- Asymptotics for transportation cost in high dimensions
- Geometric properties of Poisson matchings
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 227027 (Why is no real title available?)
- scientific article; zbMATH DE number 964350 (Why is no real title available?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
- Matching random samples in many dimensions
- On optimal matchings
- On the Stochastic Euclidean Travelling Salesperson Problem for Distributions with Unbounded Support
- Poisson matching
- Probability theory of classical Euclidean optimization problems
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- The integrability of the square exponential transportation cost
Cited in
(38)- An algorithm to approximate the optimal expected inner product of two vectors with given marginals
- Behavior of the empirical Wasserstein distance in \({\mathbb R}^d\) under moment conditions
- A PDE approach to a 2-dimensional matching problem
- Random restricted matching and lower bounds for combinatorial optimization
- Some results on the optimal matching problem for the Jacobi model
- A simple Fourier analytic proof of the AKT optimal matching theorem
- Limit theory of combinatorial optimization for random geometric graphs
- On the quadratic random matching problem in two-dimensional domains
- A fluctuation result for the displacement in the optimal matching problem
- Gravitational allocation for uniform points on the sphere
- On optimal matching of Gaussian samples
- Finer estimates on the 2-dimensional matching problem
- On the mean speed of convergence of empirical and occupation measures in Wasserstein distance
- On Kac's chaos and related problems
- Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds
- Rate of convergence of the Nanbu particle system for hard potentials and Maxwell molecules
- Parametrization of Random Vectors in Polynomial Chaos Expansions via Optimal Transportation
- Constructive quantization: approximation by empirical measures
- On the rate of convergence in Wasserstein distance of the empirical measure
- k-variance: a clustered notion of variance
- On the rate of convergence of empirical measure in -Wasserstein distance for unbounded density function
- One-dimensional empirical measures, order statistics, and Kantorovich transport distances
- Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
- Optimal transport methods for combinatorial optimization over two random point sets
- Random matching in 2D with exponent 2 for Gaussian densities
- A unifying approach to distributional limits for empirical optimal transport
- Limit distribution theory for smooth \(p\)-Wasserstein distances
- There is no stationary p-cyclically monotone Poisson matching in 2d
- Annealed quantitative estimates for the quadratic 2D-discrete random matching problem
- On minimum spanning trees for random Euclidean bipartite graphs
- Optimal matching problem on the Boolean cube
- Greedy matching in optimal transport with concave cost
- Convergence of empirical optimal transport in unbounded settings
- Wasserstein asymptotics for Brownian motion on the flat torus and Brownian interlacements
- On the concave one-dimensional random assignment problem and Young's integration theory
- Sharp convergence rates of empirical unbalanced optimal transport for spatio-temporal point processes
- Almost sharp rates of convergence for the average cost and displacement in the optimal matching problem
- Transport inequalities on Euclidean spaces for non-Euclidean metrics
This page was built for publication: Combinatorial Optimization Over Two Random Point Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2865119)
