# What is the sqrt(n)-approximation algorithm for set packing problem

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.

• 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. – David Richerby Dec 2 '15 at 8:25

See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms:
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.