The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm
Joint Authors
Lucibello, C.
Ricci-Tersenghi, F.
Source
International Journal of Statistical Mechanics
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-03-10
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
We analyse the asymptotic behaviour of random instances of the maximum set packing (MSP) optimization problem, also known as maximum matching or maximum strong independent set on hypergraphs.
We give an analytic prediction of the MSPs size using the 1RSB cavity method from statistical mechanics of disordered systems.
We also propose a heuristic algorithm, a generalization of the celebrated Karp-Sipser one, which allows us to rigorously prove that the replica symmetric cavity method prediction is exact for certain problem ensembles and breaks down when a core survives the leaf removal process.
The e-phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized to Cs=e/(d-1) for one of the ensembles considered, where d is the size of the sets.
American Psychological Association (APA)
Lucibello, C.& Ricci-Tersenghi, F.. 2014. The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm. International Journal of Statistical Mechanics،Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-448603
Modern Language Association (MLA)
Lucibello, C.& Ricci-Tersenghi, F.. The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm. International Journal of Statistical Mechanics No. 2014 (2014), pp.1-13.
https://search.emarefa.net/detail/BIM-448603
American Medical Association (AMA)
Lucibello, C.& Ricci-Tersenghi, F.. The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm. International Journal of Statistical Mechanics. 2014. Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-448603
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-448603