%0 Journal Article
%T The Statistical Mechanics of Random Set Packing and a Generalization of the Karp-Sipser Algorithm
%A C. Lucibello
%A F. Ricci-Tersenghi
%J International Journal of Statistical Mechanics
%D 2014
%R 10.1155/2014/136829
%X 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 -phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized to for one of the ensembles considered, where is the size of the sets. 1. Introduction The maximum set packing is a very much studied problem in combinatorial optimization, one of Karp¡¯s twenty-one NP-complete problems. Given a set and a collection of its subsets labeled by ; a set packing (SP) is a collection of the subsets such that they are pairwise disjoint. The size of a SP is . A maximum set packing (MSP) is an SP of maximum size. The integer programming formulation of the MSP problem reads The MSP problem, also known in the literature as the matching problem on hypergraphs or the strong independent set problem on hypergraphs, is an NP-Hard problem. This general formulation, however, can be specialized to obtain two other famous optimization problems: the restriction of the MSP problem to sets of size 2 corresponds to the problem of maximum matching on ordinary graphs and can be solved in polynomial time [1]; the restriction where each element of appears exactly 2 times in is the maximum independent set and belongs to the NP-Hard class. The formulation ((1)¨C(3)) of the MSP problem, therefore, encodes an ample class of packing problems and, as all packing problems, is related by duality to a covering problem, the minimum set covering problem. Another common specialization of the general MSP problem, known as -set packing, is that in which all sets have size at most . This is one of the most studied specializations in the computer science community, the efforts concentrating on minimal degree conditions to obtain a perfect matching [2], linear relaxations [3, 4], and approximability conditions [5¨C7]. Motivated by this interest, we choose a -set packing problem ensemble as the principal application of the general analytical framework developed in the following sections. The asymptotic behaviour of random sparse
%U http://www.hindawi.com/journals/ijsm/2014/136829/