For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem.

Given a universe $U$ and a family $ \mathcal{S} $ of subsets of $ {\mathcal{U}}$. Assume that all subsets in $\mathcal{S}$ have size $k$. A $k$-set packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}} $ of sets such that all sets in ${\mathcal{C}}$ are pairwise disjoint, and the size of the packing is $|{\mathcal {C}}|$. We are looking for the maximum size of k-Set Packing.

I have found a few math papers claiming the integrality gap is exactly $k - 1 + \frac{1}{k}$, via standard linear programming; $k - 2$, by local constraints; at most $\frac{k+1}{2}$ via a result in extremal combinatorics. However, there is no clear algorithm for implementation. Please help me if you have any suggestions. Thank you!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.