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 unsign
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
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)
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.