The Random Fractional Matching Problem
arXiv:1802.02997 · doi:10.1088/1742-5468/aabbc8
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 [Acta Mathematica 204, 91-150 (2010)], 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.
arXiv comment24 pages, 3 figures
References in corpus (13)
- Maximum Weight Matching via Max-Product Belief Propagation
- The number of matchings in random graphs
- Learning by message-passing in networks of discrete synapses
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Structured x-ray beams from twisted electrons by inverse Compton scattering of laser light
- Experimental adaptive process tomography
- The stochastic matching problem
- On the finite size corrections to some random matching problems
- Ambiguous measurements, signalling and violations of Leggett-Garg inequalities
- Quadratic stochastic Euclidean bipartite matching problem
- Simultaneous measurement of two non-commuting quantum variables: Solution of a dynamical model
- Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
- Extended necessary condition for local operations and classical communication: Tight bound for all measurements