Jump to content

Talk:Set packing

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[reply]

Example

[edit]

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)[reply]

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

What is c(s)?

[edit]

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)[reply]

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

Independent Set vs. Set Packing

[edit]

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)[reply]

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

[edit]

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 (talkcontribs) 19:47, 16 January 2018 (UTC)[reply]