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. SODA06) 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$)?
Algorithms for set packing
ds.algorithms
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$, seehttp://dx.doi.org/10.1137/070683933BTW, The parameterized result you list for $3$-sets is not the best known, seehttp://arxiv.org/abs/1007.1161for a state-of-the-art algorithm and a list of previous results on the problem.