Random assignment problems on \(2d\) manifolds. (English) Zbl 1470.60035
Summary: We consider the assignment problem between two sets of \(N\) random points on a smooth, two-dimensional manifold \(\Omega\) of unit area. It is known that the average cost scales as \(E_{\Omega}(N)\sim{1}/{2\pi}\ln N\) with a correction that is at most of order \(\sqrt{\ln N\ln\ln N}\). In this paper, we show that, within the linearization approximation of the field-theoretical formulation of the problem, the first \(\Omega\)-dependent correction is on the constant term, and can be exactly computed from the spectrum of the Laplace-Beltrami operator on \(\Omega\). We perform the explicit calculation of this constant for various families of surfaces, and compare our predictions with extensive numerics.
MSC:
| 60D05 | Geometric probability and stochastic geometry |
| 35P20 | Asymptotic distributions of eigenvalues in context of PDEs |
| 49Q20 | Variational problems in a geometric measure-theoretic setting |
| 53C21 | Methods of global Riemannian geometry, including PDE methods; curvature restrictions |
Keywords:
matching; assignment; random optimization problems; optimal transportation; finite-size corrections; disorderReferences:
| [1] | Caracciolo, S., Lucibello, C., Parisi, G., Sicuro, G.: Scaling Hypothesis for the Euclidean Bipartite Matching Problem. Phys. Rev. E 90 012118 (2014) |
| [2] | Caracciolo, S., Sicuro, G.: Quadratic Stochastic Euclidean Bipartite Matching Problem. Phys. Rev. Lett. 115, 230601 (2015) |
| [3] | Ambrosio, L.; Stra, F.; Trevisan, D., A PDE approach to a 2-dimensional matching problem, Prob. Theory Relat. Fields, 173, 433-477 (2019) · Zbl 1480.60017 · doi:10.1007/s00440-018-0837-x |
| [4] | Ambrosio, L.; Glaudo, F., Finer estimates on the 2-dimensional matching problem, J. Éc. Polytech. Math., 6, 737-765 (2019) · Zbl 1434.60054 · doi:10.5802/jep.105 |
| [5] | Okikiolu, K., A Negative Mass Theorem for the 2-Torus, Commun. Math. Phys., 284, 775-802 (2008) · Zbl 1167.53038 · doi:10.1007/s00220-008-0644-9 |
| [6] | Okikiolu, K., A negative mass theorem for surfaces of positive genus, Commun. Math. Phys., 290, 1025-1031 (2009) · Zbl 1184.53046 · doi:10.1007/s00220-008-0722-z |
| [7] | Kuhn, HW, The Hungarian method for the assignment problem, Nav. Res. Logist., 2, 83-97 (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109 |
| [8] | Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325-340 (1987) ISSN 0010485X · Zbl 0607.90056 |
| [9] | Lovász, L., Plummer, M. D.: Matching Theory (AMS Chelsea Publishing Series vol 367) (North-Holland; Elsevier Science Publishers B.V.) (2009) ISBN 78-0-8218-4759-6 · Zbl 1175.05002 |
| [10] | Orland, H., Mean-field theory for optimization problems, Le J. Phys. (Paris) Lett., 46, 770-773 (1985) |
| [11] | Mézard, M., Parisi, G.: Replicas and optimization. J. Phys. (Paris) Lett. 46, 771-778 (1985). ISSN 0302-072X |
| [12] | Mézard, M.; Parisi, G., Mean-field equations for the matching and the travelling salesman problems, Europhys. Lett., 2, 913-918 (1986) · doi:10.1209/0295-5075/2/12/005 |
| [13] | Aldous, D. J.: The \(\zeta (2)\) limit in the random assignment problem. Random Struct. Algorithms 2, 381-418 (2001) · Zbl 0993.60018 |
| [14] | Nair, C., Prabhakar, B., Sharma, M.: Proofs of the Parisi and Coppersmith-Sorkin conjectures for the finite random assignment problem 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (IEEE Computer. Soc) pp 168-178 (2003). ISBN 0-7695-2040-5 |
| [15] | Linusson, S.; Wästlund, J., A proof of Parisi’s conjecture on the random assignment problem, Prob. Theory Relat. Fields, 128, 419-440 (2004) · Zbl 1055.90056 · doi:10.1007/s00440-003-0308-9 |
| [16] | Mézard, M.; Parisi, G., The Euclidean matching problem, J. Phys. (Paris), 49, 2019-2025 (1988) · doi:10.1051/jphys:0198800490120201900 |
| [17] | Lucibello, C., Parisi, G., Sicuro, G.: One-loop diagrams in the random Euclidean matching problem. Phys. Rev. E 95, 012302 (2017). ISSN 2470-0045 (Preprint 1609.09310) |
| [18] | Ajtai, M.; Komlós, J.; Tusnády, G., On optimal Matchings, Combinatorica, 4, 259-264 (1984) · Zbl 0562.60012 · doi:10.1007/BF02579135 |
| [19] | Benedetto, D., Caglioti, E.: Euclidean random matching in 2d for non-constant densities (Preprint 1911.10523) (2019) · Zbl 1458.60020 |
| [20] | Saff, EB; Kuijlaars, ABJ, Distributing many points on a sphere, Math. Intell., 19, 5-11 (1997) · Zbl 0901.11028 · doi:10.1007/BF03024331 |
| [21] | Rakhmanov, EA; Saff, EB; Zhou, YM, Minimal discrete energy on the sphere, Math. Res. Lett., 1, 647-662 (1994) · Zbl 0839.31011 · doi:10.4310/MRL.1994.v1.n6.a3 |
| [22] | Ambrosio, L.: Lecture notes on optimal transport problems (2003) · Zbl 1047.35001 |
| [23] | Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows: In Metric Spaces and in the Space of Probability Measures Lectures in Mathematics. ETH Zürich (Birkhäuser Basel) (2006). ISBN 9783764373092 |
| [24] | Villani, C.: Optimal transport: old and new vol 338. Springer Science & Business Media (2008) · Zbl 1156.53003 |
| [25] | Fathi, A.; Figalli, A., Optimal transportation on non-compact manifolds, Isr. J. Math., 175, 1-59 (2010) · Zbl 1198.49044 · doi:10.1007/s11856-010-0001-5 |
| [26] | Caracciolo, S., Sicuro, G.: Scaling hypothesis for the Euclidean bipartite matching problem. II. Correlation functions. Phys. Rev. E 91, 062125 (2015) |
| [27] | Born, M., Infeld, L.: Foundations of the New Field. Proc. R. Soc. Lond. A 144 425-451 (1934) · Zbl 0008.42203 |
| [28] | Brenier, Y., Derivation of the Euler Equations from a Caricature of Coulomb Interaction, Commun. Math. Phys., 212, 93-104 (2000) · Zbl 1025.82012 · doi:10.1007/s002200000204 |
| [29] | Brenier, Y., A note on deformations of 2D fluid motions using 3D Born-Infeld equations, Monatsh. Math., 142, 113-122 (2004) · Zbl 1063.35130 · doi:10.1007/s00605-004-0240-9 |
| [30] | Ivrii, V., 100 years of Weyl’s law, Bull. Math. Sci., 6, 379-452 (2016) · Zbl 1358.35075 · doi:10.1007/s13373-016-0089-y |
| [31] | Duistermaat, J.J., Guillemin, V.W.: The spectrum of positive elliptic operators and periodic bicharacteristics. Invent. Math. 39-79, (1975) · Zbl 0307.35071 |
| [32] | Strauss, WA, Partial Differential Equations (2008), New York: Wiley, New York · Zbl 1160.35002 |
| [33] | Ambrosio, L., Glaudo, F., Trevisan, D.: On the optimal map in the 2-dimensional random matching problem. Discrete Cont. Dyn. A 39, 1078-0947 (2019) · Zbl 1476.60020 |
| [34] | Apostol, TM, Modular Functions and Dirichlet Series in Number Theory Graduate Texts in Mathematics (2012), New York: Springer, New York |
| [35] | Osgood, B., Phillips, R., Sarnak, P.: Extremals of determinants of Laplacians. J. Funct. Anal. 80 148 - 211 (1988). ISSN 0022-1236 · Zbl 0653.53022 |
| [36] | Morpurgo, C., Sharp inequalities for functional integrals and traces of conformally invariant operators, Duke Math. J., 114, 477-553 (2002) · Zbl 1065.58022 · doi:10.1215/S0012-7094-02-11433-1 |
| [37] | Steiner, J., A geometrical mass and its extremal properties for metrics on \(S^2\), Duke Math. J., 129, 63-86 (2005) · Zbl 1144.53055 · doi:10.1215/S0012-7094-04-12913-6 |
| [38] | Okikiolu, K., Extremals for logarithmic Hardy-Littlewood-Sobelov inequalities on compact manifolds, Geom. Funct. Anal., 17, 1655-1684 (2008) · Zbl 1140.58003 · doi:10.1007/s00039-007-0636-5 |
| [39] | Boniolo, E., Caracciolo, S., Sportiello, A.: Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle. J. Stat. Mech. 11 P11023 (2014) · Zbl 1456.91064 |
| [40] | Lin, C.S., Wang, C.L.: Elliptic functions, Green functions and the mean field equations on tori. Ann. Math. 911-954, (2010) · Zbl 1207.35011 |
| [41] | Elizalde, E.; Leseduarte, S.; Romeo, A., Sum rules for zeros of Bessel functions and an application to spherical Aharonov-Bohm quantum bags, J. Phys. A Math. Gen., 26, 2409-2419 (1993) · Zbl 0791.33003 · doi:10.1088/0305-4470/26/10/012 |
| [42] | Holden, N., Peres, Y., Zhai, A.: Gravitational allocation on the sphere. Proc. Natl. Acad. Sci. USA 115 9666-9671 (2018). ISSN 0027-8424 · Zbl 1419.60010 |
| [43] | Erdélyi, A., Magnus, W., Oberhettinger, F., Tricomi, F.G.: Higher Transcendental Functions (Krieger) (1981) |
| [44] | Siegel, C. L.: Lectures on Advanced Analytic Number Theory Lectures on mathematics and physics: Mathematics (Tata Institute of Fundamental Research) (1965) · Zbl 0278.10001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
