4
$\begingroup$

The set packing problem is : Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of the packing is $|C|$. The goal is to find the $C$ where $|C|$ is maximum.

According to Wikipedia, there exists a $\sqrt{|U|}$-approximation algorithm for this problem. But it doesn't give a way to approach that, it seems that the way cannot be found on google as well.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ The notation $\{S\}$ means "The set whose only element is $S$" not "$S$ is a set." $S$ and $\{S\}$ are completely different objects: you can think of $S$ as a box containing things; $\{S\}$ is a box containing a box containing those things. $\endgroup$ – David Richerby Dec 2 '15 at 8:25
4
$\begingroup$

See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms:

  • Unweighted case: Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998), "Independent sets with domination constraints", Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185.

  • Weighted case: Halldórsson, M. M. (1999a), "Approximations of weighted independent set and hereditary subset problems", Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci., Springer-Verlag, 261-270.

I found this link on the first page of the Google search set packing approximation algorithm. I suggest that next time you spend some quality time with your favorite search engine, looking at all links in the first few pages.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.