Talk:Set packing

I am very astonished that this NP hard problem can be solved in a complexity in O(\sqrt{|S|}), could you show us the proof of what you say? —Preceding unsigned comment added by 130.66.124.6 (talk) 09:23, August 29, 2007 (UTC)

I agree, there should be at least a reference to the paper mentioning the approximation algorithm. --Erel Segal (talk) 13:08, 8 December 2013 (UTC)

Example

This example is terribly convoluted. Could we get one that contributes to understanding the problem, rather than confuses the reader even more? 76.104.24.220 (talk) 22:37, 30 November 2010 (UTC)

Added a simpler example. What do you think? --Erel Segal (talk) 08:50, 9 December 2013 (UTC)

What is c(s)?

In the "Integer linear program formulation" section, what is c(S)? It seems redundant. --109.67.198.87 (talk) 06:40, 6 December 2013 (UTC)

Fixed. --Erel Segal (talk) 13:07, 8 December 2013 (UTC)

Independent Set vs. Set Packing

The article says that Independent set (graph theory) is a special case of set packing. But it seems to me that these problems are equivalent - there is a bidirectional one-to-one reduction between them (see: http://cs.stackexchange.com/questions/18736/equivalence-of-independent-set-and-set-packing ). Is this correct? --Erel Segal (talk) 13:08, 8 December 2013 (UTC)

Independent set is equivalent in complexity terms, but not in terms of computation effort needed to solve.

There are cut-offs possible in the weighted set packing problem that are not possible in the corresponding weighted independent set problem. See https://cs.stackexchange.com/q/86848/83094 for an example. I think that this must be clarified, since people who need to actually solve instances of the weighted packing problem optimally would not do any good by using a weighted independent set solver. — Preceding unsigned comment added by Mgoldenbe (talk • contribs) 19:47, 16 January 2018 (UTC)