scientific article; zbMATH DE number 3943557

From MaRDI portal
Publication:3714899





[For the entire collection see Zbl 0572.00022.] The maximum cardinality set packing problem (SPP), formulated as \(\max \{e_ nx:\) \(Ax\leq e_ m\), \(x\in \{0,1\}^ n\}\), where A is an \(m\times n\) binary matrix and \(e_ n\), \(e_ m\) are vectors of 1's of appropriate size, is a well-known NP-hard integer programming problem arising in a number of real-world applications. In this paper, a probabilistic analysis of the SPP is developed, considering a stochastic model of the incidence matrix A in which the entries are independent Bernoulli distributed random variables, each with probability \(p_ n\) of being equal to 1. A threshold function \(t_ k(n,p_ n)\) on the number m of constraints is derived for the property that a packing of cardinality k exists with probability tending to one as n tends to infinity. In particular, it is shown that, if the probability \(p_ n\) is constant, then the optimum value is almost surely equal to 1; thus, combining the latter result with the corresponding one for the SCP obtained by the author in a previous paper [Ann. Oper. Res. 1 (1984)], the duality gap is analyzed and shown to be asymptotically large as log n in ratio almost surely. Finally, the performance of the simple blind sequential algorithm is investigated, and a sufficient condition is assigned which the sequences \(p_ n\) and \(m_ n\) have to satisfy for the ratio of the optimal solution value to the approximate one to be asymptotically bounded by 2 almost surely.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3714899)