The random fractional matching problem

DOI10.1088/1742-5468/AABBC8MaRDI QIDQ4964595zbMATH OpenOpenAlexWikidataFDO

Authors Carlo Lucibello, Enrico M. Malatesta, Gabriele Sicuro, G. Parisi

Publication date 2 March 2021

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72) Stochastic programming (90C15) Combinatorial optimization (90C27)

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"{a}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.

Recommendations

• Random-link matching problems on random regular graphs
• Random matching problems on the complete graph
• Convergence of asymptotic costs for random Euclidean matching problems
• Constructive bounds and exact expectations for the random assignment problem
• The Euclidean Matching Problem

Cites work

• A proof of Parisi's conjecture on the random assignment problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Algorithms for the Assignment and Transportation Problems
• Asymptotics in the random assignment problem
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• Information, Physics, and Computation
• Matching theory
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Optimization by simulated annealing
• Phase transitions in semidefinite relaxations
• Random matching problems on the complete graph
• Survey propagation: An algorithm for satisfiability
• The (2) limit in the random assignment problem
• The mean field traveling salesman and related problems

Cited in

(6)

• On the use of optimal fractional matchings for solving the (integer) matching problem
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• Replica symmetry of the minimum matching
• Exact solution of the random bipartite matching model
• Random multi-index matching problems
• Random-link matching problems on random regular graphs

This page was built for publication: The random fractional matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4964595)