1
$\begingroup$

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!

$\endgroup$

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.