![](/images/graphics-bg.png)
The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm
المؤلفون المشاركون
Lucibello, C.
Ricci-Tersenghi, F.
المصدر
International Journal of Statistical Mechanics
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-13، 13ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-03-10
دولة النشر
مصر
عدد الصفحات
13
التخصصات الرئيسية
الملخص 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.
نمط استشهاد جمعية علماء النفس الأمريكية (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
نمط استشهاد الجمعية الأمريكية للغات الحديثة (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
نمط استشهاد الجمعية الطبية الأمريكية (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
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-448603
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)