The random fractional matching problem. (3rd May 2018)

• Record Type: Journal Article
• Authors: Lucibello, Carlo; Malatesta, Enrico M; Parisi, Giorgio; Sicuro, Gabriele
• Is Part Of: Journal of statistical mechanics. (2018:May)
• Publication Date: 2018-05-03
• Subjects: 7 -- 11; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/aabbc8
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: We consider two formulations of the random-link fractional matching problem, a relaxed version of the more standard random-link (integer) matching problem. In one formulation, we allow each node to be linked to itself in the optimal matching configuration. In the other one, on the contrary, such a link is forbidden. Both problems have the same asymptotic average optimal cost of the random-link matching problem on the complete graph. Using a replica approach and previous results of Wästlund (2010 Acta Mathematica 204 91–150), we analytically derive the finite-size corrections to the asymptotic optimal cost. We compare our results with numerical simulations and we discuss the main differences between random-link fractional matching problems and the random-link matching problem.