18
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Google ? "set packing" ? en.wikipedia.org/wiki/Set_packing this is not a research level question yet (see our FAQ). Closing now... $\endgroup$ – Suresh Venkat Dec 25 '10 at 5:07
  • 1
    $\begingroup$ @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? $\endgroup$ – Travis Service Dec 25 '10 at 16:36
  • 3
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Dec 25 '10 at 17:53
  • 3
    $\begingroup$ I'd advocate reopening this question. "Time complexity" usually refers to exact algorithms, unless stated otherwise, no? $\endgroup$ – arnab Dec 27 '10 at 5:12
  • 7
    $\begingroup$ This question should be reopened. $\endgroup$ – Peter Shor Dec 30 '10 at 2:25
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.