Talk:Set packing

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Start	This article has been given a rating which conflicts with the project-independent quality rating in the banner shell. Please resolve this conflict if possible.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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

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)?

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

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.

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