Scaling hypothesis for the Euclidean bipartite matching problem.

Area of Science:

• Mathematical Physics
• Computational Geometry
• Optimization Theory

Background:

• The Euclidean bipartite matching problem is a fundamental problem in computational geometry and optimization.
• Existing methods often struggle to provide analytic predictions for large numbers of points (N) or in higher dimensions.
• Understanding the cost dependence on point density is crucial for developing efficient algorithms.

Purpose of the Study:

• To develop a simple, predictive model for the functional dependence of cost on point density in Euclidean bipartite matching.
• To derive analytic predictions for the large N limit of the average cost and subleading corrections.
• To investigate the scaling behavior of these corrections in different dimensions.

Main Methods:

• Formulation of a cost function based on Poisson's equation.
• Analytic calculations for quadratic costs in dimensions d=1 and d=2.
• Analysis of subleading corrections in higher dimensions (d>2).

Main Results:

• A predictive functional form for the cost dependence on point density.
• Analytic prediction of the large N average cost in d=1, 2.
• Identification of a nontrivial scaling exponent, γ(d) = (d-2)/d, for subleading corrections in higher dimensions.
• Evidence that this scaling holds for generic cost exponents in d>2.

Conclusions:

• The proposed model offers accurate analytic predictions for the Euclidean bipartite matching problem.
• The identified scaling exponent for subleading corrections differs from the monopartite case, highlighting unique aspects of bipartite matching.
• The findings have implications for theoretical understanding and algorithmic development in optimization and computational geometry.