Title :
Bypassing correlation decay for matchings with an application to XORSAT
Author_Institution :
INRIA-ENS, Paris, France
Abstract :
Many combinatorial optimization problems on sparse graphs do not exhibit the correlation decay property. In such cases, the cavity method remains a sophisticated heuristic with no rigorous proof. In this paper, we consider the maximum matching problem which is one of the simplest such example. We show that monotonicity properties of the problem allows us to define solutions for the cavity equations. More importantly, we are able to identify the `right´ solution of these equations and then to compute the asymptotics for the size of a maximum matching. The results for finite graphs are self-contained. We give references to recent extensions making use of the notion of local weak convergence for graphs and the theory of unimodular networks. As an application, we consider the random XORSAT problem which according to the physics literature has a `one-step replica symmetry breaking´ (1RSB) glass phase. We derive new bounds on the satisfiability threshold valid for general graphs (and conjectured to be tight).
Keywords :
combinatorial mathematics; graph theory; optimisation; 1RSB; bypassing correlation decay; cavity equations; cavity method; combinatorial optimization problems; correlation decay property; finite graphs; monotonicity properties; one-step replica symmetry breaking; random XORSAT problem; sparse graphs; unimodular networks. theory; Algorithm design and analysis; Bipartite graph; Cavity resonators; Convergence; Correlation; Equations; Vectors;
Conference_Titel :
Information Theory Workshop (ITW), 2013 IEEE
Conference_Location :
Sevilla
Print_ISBN :
978-1-4799-1321-3
DOI :
10.1109/ITW.2013.6691322