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. Thee-phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized toCs=e/(d-1)for one of the ensembles considered, wheredis the size of the sets.
展开▼
机译：我们分析最大集包装（MSP）优化问题的随机实例的渐近行为，也称为超图上的最大匹配或最大强独立集。我们使用1RSB腔方法从无序系统的统计力学中得出MSP大小的解析预测。我们还提出了一种启发式算法，该算法是著名的Karp-Sipser算法的推广，可以使我们严格证明对于某些问题，复制对称腔方法的预测是准确的，并且当核心在除叶过程中存活下来时，该方法会崩溃。由Karp和Sipser发现的e-现象阈值，标志着核心出现和复制对称性断裂的开始，被优雅地推广到所考虑的其中一个集合的Cs = e /（d-1），其中集合的大小。
展开▼
