<p>You mention <a href="https://cs.stackexchange.com/questions/18736/equivalence-of-independent-set-and-set-packing">Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06</a>. There seems to be a <a href="https://cs.stackexchange.com/questions/18736/equivalence-of-independent-set-and-set-packing">one-to-one polynomial-time reduction between independent-set and set-packing</a>. Therefore, the results for the independent set problem should be applicable to set packing as well.</p>

CC BY-SA 3.0
2013-12-09T09:15:58.750Z
2013-12-09T09:15:58.750Z
2017-04-13T12:48:30.830Z
Erel Segal-Halevi
<p>Indeed, set packing, partitioning, and covering have been studied in terms of exact algorithm running times.
 To address your last question, you can solve weighted set packing in $O(m2^n)$ time by dynamic programming across all subsets of $[n]$.
 Moreover, if your integer weights are bounded by $M$, you can solve it in $O(M2^n)$ time, even if $m$ is as large as $2^n$, see</p>

<p><a href="http://dx.doi.org/10.1137/070683933" rel="noreferrer">http://dx.doi.org/10.1137/070683933</a></p>

<p>BTW, The parameterized result you list for $3$-sets is not the best known, see</p>

<p><a href="http://arxiv.org/abs/1007.1161" rel="noreferrer">http://arxiv.org/abs/1007.1161</a></p>

<p>for a state-of-the-art algorithm and a list of previous results on the problem.</p>

CC BY-SA 2.5
2010-12-31T11:20:12.230Z
2010-12-31T11:20:12.230Z
Andreas Björklund
<p>There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along these lines for some NP-hard problems (e.g., <a href="http://dl.acm.org/citation.cfm?id=1109560" rel="nofollow">Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06</a>) but I haven't been able to find similar work for the set packing problem. There seems to be similar work on some restrictions of the set packing problem (e.g., An $O^{*}(3.523^{k})$ Parameterized Algorithm for 3-Set Packing) but I haven't found any for the general set packing problem.</p>

<p>So my question is: What is the best time complexity for exactly solving the weighted set packing problem where there are $m$ sets drawn from a universe of $n$ elements?</p>

<p>I am also interested in the relationship between the number of sets and the size of the universe. For example, has there been algorithmic work on situations where $m$ is relatively large compared to $n$ (i.e., close to $2^n$)?</p>

CC BY-SA 2.5
2010-12-25T05:07:18.673Z
Google ? "set packing" ? http://en.wikipedia.org/wiki/Set_packing this is not a research level question yet (see our FAQ). Closing now...
Suresh Venkat
CC BY-SA 2.5
2010-12-25T16:36:58.210Z
@Suresh, I am interested in results of the form: Algorithm A solves the set packing problem in O(c^n) time, with c small. There is such work for other NP-hard problems (e.g., Measure and conquer: a simple O(2^0.288n) independent set algorithm. SODA’06). The wikipedia article you link doesn't discuss this and I have not found any recent articles discussing set packing's time complexity. Most work I have found is on the k-set packing problem. This is a "request-for-reference" type question. Are these sort of questions welcome here? or perhaps the question was not written well enough?
Travis Service
CC BY-SA 2.5
2010-12-25T17:53:11.580Z
That makes a lot more sense actually. the key point is that you are looking for EXACT algorithms for weighted set packing. If you'd like to reword, provide any references for $k$-set packing (as well as what it is), then I'd be happy to reopen - just flag it for moderator attention.
Suresh Venkat
CC BY-SA 2.5
2010-12-27T05:12:22.517Z
I'd advocate reopening this question.  "Time complexity" usually refers to exact algorithms, unless stated otherwise, no?
arnab
CC BY-SA 2.5
2010-12-27T08:42:56.130Z
@Travis Service: Your comment [shows that you care about your own question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304), which is a good thing.  It is better to put that comment as part of the question.  Please edit the question so that people can understand more about the question without reading the comments, and then flag the question for the moderator attention to ask them to reopen it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-28T17:29:05.870Z
As I said, I'm happy to reopen. I'm waiting for the OP to edit the question.
Suresh Venkat
CC BY-SA 2.5
2010-12-30T02:25:51.100Z
This question should be reopened.
Peter Shor 
CC BY-SA 2.5
2010-12-30T17:10:59.100Z
another good reason why we need more moderators in different time zones :). sorry for the delay
Suresh Venkat
<ds.algorithms>
Algorithms for set packing
Travis Service
# Algorithms for set packing

(Asked by: username_0 on 2010-12-24)

There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along these lines for some NP-hard problems (e.g., [Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06](http://dl.acm.org/citation.cfm?id=1109560)) but I haven't been able to find similar work for the set packing problem. There seems to be similar work on some restrictions of the set packing problem (e.g., An $O^{\*}(3.523^{k})$ Parameterized Algorithm for 3-Set Packing) but I haven't found any for the general set packing problem.

So my question is: What is the best time complexity for exactly solving the weighted set packing problem where there are $m$ sets drawn from a universe of $n$ elements?

I am also interested in the relationship between the number of sets and the size of the universe. For example, has there been algorithmic work on situations where $m$ is relatively large compared to $n$ (i.e., close to $2^n$)?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Google ? "set packing" ? http://en.wikipedia.org/wiki/Set_packing this is not a research level question yet (see our FAQ). Closing now...  
> **username_0**: @Suresh, I am interested in results of the form: Algorithm A solves the set packing problem in O(c^n) time, with c small. There is such work for other NP-hard problems (e.g., Measure and conquer: a simple O(2^0.288n) independent set algorithm. SODA’06). The wikipedia article you link doesn't discuss this and I have not found any recent articles discussing set packing's time complexity. Most work I have found is on the k-set packing problem. This is a "request-for-reference" type question. Are these sort of questions welcome here? or perhaps the question was not written well enough?  
> **username_1**: That makes a lot more sense actually. the key point is that you are looking for EXACT algorithms for weighted set packing. If you'd like to reword, provide any references for $k$-set packing (as well as what it is), then I'd be happy to reopen - just flag it for moderator attention.  
> **username_2**: I'd advocate reopening this question.  "Time complexity" usually refers to exact algorithms, unless stated otherwise, no?  
> **username_3**: @Travis Service: Your comment [shows that you care about your own question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304), which is a good thing.  It is better to put that comment as part of the question.  Please edit the question so that people can understand more about the question without reading the comments, and then flag the question for the moderator attention to ask them to reopen it.  
> **username_1**: As I said, I'm happy to reopen. I'm waiting for the OP to edit the question.  
> **username_4**: This question should be reopened.  
> **username_1**: another good reason why we need more moderators in different time zones :). sorry for the delay  

---

## 2 answers

### Answer by username_6 on 2010-12-31. Score: 13 | Accepted answer

Indeed, set packing, partitioning, and covering have been studied in terms of exact algorithm running times.
To address your last question, you can solve weighted set packing in $O(m2^n)$ time by dynamic programming across all subsets of $[n]$.
Moreover, if your integer weights are bounded by $M$, you can solve it in $O(M2^n)$ time, even if $m$ is as large as $2^n$, see

<http://dx.doi.org/10.1137/070683933>

BTW, The parameterized result you list for $3$-sets is not the best known, see

<http://arxiv.org/abs/1007.1161>

for a state-of-the-art algorithm and a list of previous results on the problem.


---

### Answer by username_5 on 2013-12-09. Score: 2

You mention [Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06](https://cs.stackexchange.com/questions/18736/equivalence-of-independent-set-and-set-packing). There seems to be a [one-to-one polynomial-time reduction between independent-set and set-packing](https://cs.stackexchange.com/questions/18736/equivalence-of-independent-set-and-set-packing). Therefore, the results for the independent set problem should be applicable to set packing as well.


---

