Anomalous scaling of the optimal cost in the one-dimensional random assignment problem

DOI10.1007/s10955-018-2212-9zbMath1451.90137arXiv1803.04723OpenAlexW3100577386MaRDI QIDQ1731012

Sergio Caracciolo, Matteo D'Achille, Gabriele Sicuro

Publication date: 6 March 2019

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.04723

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

On the quadratic random matching problem in two-dimensional domains, Euclidean random matching in 2D for non-constant densities, Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, The number of optimal matchings for Euclidean assignment on the line, The Dyck bound in the concave 1-dimensional random assignment model, On optimal matching of Gaussian samples III

Cites Work

• Unnamed Item
• Unnamed Item
• Weak and strong convergence of derivations and stability of flows with respect to MGH convergence
• On optimal matchings
• Asymptotics in the random assignment problem
• A proof of Parisi's conjecture on the random assignment problem
• Scaling and non-standard matching theorems
• Asymptotics for \(L_2\) functionals of the empirical quantile process, with applications to tests of fit based on weighted Wasserstein distances
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Information, Physics, and Computation
• Exact solutions to the transportation problem on the line
• Average optimal cost for the Euclidean TSP in one dimension
• Survey propagation: An algorithm for satisfiability
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Optimal Transport