patternMinor
What is the sqrt(n)-approximation algorithm for set packing problem
Viewed 0 times
problemtheapproximationwhatpackingsqrtalgorithmforset
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.
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.
Solution
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
-
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.Context
StackExchange Computer Science Q#50215, answer score: 4
Revisions (0)
No revisions yet.