On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality

Abstract

We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatoric problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.

References in corpus (2)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Planar diagrams from optimization

Cited by in corpus (15)

• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Quadratic stochastic Euclidean bipartite matching problem
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Euclidean random matching in 2D for non-constant densities
• Random Euclidean matching problems in one dimension
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• One-loop diagrams in the Random Euclidean Matching Problem
• The Dyck bound in the concave 1-dimensional random assignment model
• Finite-size corrections in the random assignment problem
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Selberg integrals in 1D random Euclidean optimization problems
• The number of optimal matchings for Euclidean Assignment on the line
• Average optimal cost for the Euclidean TSP in one dimension
• The p-Airy distribution