<p>Not exactly what I was asking for, but I've noticed that this problem is $FPT$ with respect to $k$ (while Set Packing seems to be $W[1]-hard$ with respect to the required number of sets alone (i.e. without bound on the set sizes)).</p>

<p>The algorithm utilizes the famous <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;uact=8&amp;ved=0CCcQFjAA&amp;url=http://www.tau.ac.il/~nogaa/PDFS/col5.pdf&amp;ei=_sooU7eACqmY4wTk0IDoDg&amp;usg=AFQjCNH3yxDvNfSlKUXUNL9ZgZ38Mu6emg&amp;sig2=r4wfkYm-o22WObADUNYPjg&amp;bvm=bv.62922401,d.bGQ" rel="nofollow">color coding</a> scheme in the following way:</p>

<p>-Notice that we can assume w.l.o.g that all set sizes are at most $k-1$ (otherwise we can select the single largest set).</p>

<ol>
<li>"Guess" (i.e. go over all possibilities) the number of elements in the minimal feasible disjoint cover, $x$. Since the sets are of size $\leq k-1$, the smallest feasible cover is of size $k\leq x \leq 2(k-1)$.</li>
<li>Randomly color all items by $x$ colors. Denote the coloring by $C$.</li>
<li>Use dynamic programming to figure if if a set $S\subseteq [x]$ of item colors can be obtained by selecting disjoint sets. Formally, each cell in our matrix $A$ will be some subset of $[x]$, our initialization will be $A[\emptyset]=true$, and our computation will be $A[t]=\vee_{t'\subset t}\{((A[t']) \wedge (\exists s\in \mathcal{S}:C(s)\cap A[t']=\emptyset)\wedge (t'\cup C(s)=t)\}$. Basically, $A$ is a boolean matrix denoting if some set $t\subset [x]$ of colors is coverable by disjoint sets.</li>
</ol>

<p>(from this point is basically follows the CC analysis):</p>

<p>Assuming there was a disjoint cover of size $x$, the probability that all of it's elements will be colored by different colors is $\frac{x!}{x^x}\leq e^{-x}$.</p>

<p>This means that if we repeat steps 2,3 for $O(e^x)$ iterations, we will get a coloring such that with high probability we will be able to cover all $x$ colors in the DP procedure.</p>

<p>The total running time will be $O((2e)^{2k}\cdot poly(n,m))\approx O^*(29.56^k)$.</p>

<p>Using the same method of computing a $k$-perfact hashing family (instead of the random coloring), this result can also be derandomized with an increase factor of $2^{polylogk}$ to the runtime.</p>

CC BY-SA 3.0
2014-03-18T23:11:15.360Z
2014-03-19T16:54:34.400Z
2014-03-19T16:54:34.400Z
R B
<p>Optimization version of 3D matching is a special case of your problem. Approximating <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node143.html" rel="nofollow">Maximum 3D Matching</a> is $APX$-complete. However, it is approximable within 3/2$+\epsilon $ for any  $\epsilon &gt;0$</p>

<p>References:</p>

<p>Hurkens, C. A. J., and Schrijver, A. (1989), On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, 
SIAM J. Disc. Math. 2, 68-72. </p>

<p>Kann, V. (1991), Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. Process. Lett. 37, 27-35. </p>

CC BY-SA 3.0
2014-03-09T16:03:09.253Z
2014-03-09T16:18:13.173Z
2014-03-09T16:18:13.173Z
Mohammad Al-Turkistany
<p>We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.</p>

<p><strong>Set-Packing</strong> asks how many disjoint sets we can pack, and is defined as follows:</p>

<p>Given a number $k\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that all of the sets in $\mathcal{S'}$ are disjoint?</p>

<p><strong>Maximum-Coverage</strong>, allows intersecting sets, but asks how much of the universe can we cover by $k$ sets:</p>

<p>Given numbers $k\in[m]$,$r\in[n]$ is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that $|\cup_{s\in\mathcal{S''}}s|\geq r$?</p>

<hr>

<p>I'm interested in what seems to be a combination of the two, a disjoint cover, which aims at covering as much of $\mathcal{U}$ as possible.</p>

<p><strong>Disjoint-Maximum-Coverage</strong>:</p>

<p>Is there a set $\mathcal{S'} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S'}}s|\geq k$ (i.e. it covers at least $k$ elements) <strong>and</strong> the sets in $\mathcal{S'}$ are disjoint?</p>

<p><strong>What can we say about the approximation hardness of $DMC$?</strong>
Is this problem known under a different name?</p>

<p>Related results:</p>

<p>Both <strong>Set-Packing</strong> and <strong>Maximum-Coverage</strong> are known to be $APX$-Hard (and even stronger than that - Unless $P=NP$, $SP$ can't be approximated within $ln(|S|)(1-o(1))$, and $MC$ has a tight bound using the greedy algorithm).</p>

<p>$MC$ is approximable within $1-\frac{1}{e} + o(1)$, while the best known bound for $SP$ is a $O(\sqrt S)$ approximation.</p>

CC BY-SA 3.0
2014-03-09T10:59:33.763Z
Optimization version of 3D matching is a special case of your problem and approximating 3D matching is APX-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-03-09T15:43:22.613Z
Thanks @MohammadAl-Turkistany (you can add it as an answer).
Do you see an easy way to get a stronger inapproximability result?
I'm not sure if this problem is approximable within a constant factor.
R B
CC BY-SA 3.0
2014-03-09T23:08:37.193Z
Your problem is likely to be as hard as maximum independent set. MIS is hard to approximate in graphs with uniform degree and MIS can be reduced to set packing. Putting the two together should give the result.
Chandra Chekuri
CC BY-SA 3.0
2014-03-18T23:32:44.823Z
@ChandraChekuri, thanks for your response.

I'm not sure about approximability hardness, but it seems that this problem is $FPT$ while IS is $W[1]-complete$ (see my answer below).
R B
<cc.complexity-theory><ds.algorithms><complexity-classes><approximation-algorithms><approximation-hardness>
Set packing with maximum coverage objective
R B
# Set packing with maximum coverage objective

(Asked by: username_0 on 2014-03-09)

We are given a universe $\mathcal{U}=\{e\_1,..,e\_n\}$ and a set of subsets $\mathcal{S}=\{s\_1,s\_2,...,s\_m\}\subseteq 2^\mathcal{U}$.

**Set-Packing** asks how many disjoint sets we can pack, and is defined as follows:

Given a number $k\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$, $|\mathcal{S'}|=k$ such that all of the sets in $\mathcal{S'}$ are disjoint?

**Maximum-Coverage**, allows intersecting sets, but asks how much of the universe can we cover by $k$ sets:

Given numbers $k\in[m]$,$r\in[n]$ is there a set $\mathcal{S'} \subseteq \mathcal{S}$, $|\mathcal{S'}|=k$ such that $|\cup\_{s\in\mathcal{S''}}s|\geq r$?

---

I'm interested in what seems to be a combination of the two, a disjoint cover, which aims at covering as much of $\mathcal{U}$ as possible.

**Disjoint-Maximum-Coverage**:

Is there a set $\mathcal{S'} \subseteq \mathcal{S}$ such that $|\cup\_{s\in\mathcal{S'}}s|\geq k$ (i.e. it covers at least $k$ elements) **and** the sets in $\mathcal{S'}$ are disjoint?

**What can we say about the approximation hardness of $DMC$?**
Is this problem known under a different name?

Related results:

Both **Set-Packing** and **Maximum-Coverage** are known to be $APX$-Hard (and even stronger than that - Unless $P=NP$, $SP$ can't be approximated within $ln(|S|)(1-o(1))$, and $MC$ has a tight bound using the greedy algorithm).

$MC$ is approximable within $1-\frac{1}{e} + o(1)$, while the best known bound for $SP$ is a $O(\sqrt S)$ approximation.

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, approximation-algorithms, approximation-hardness

> **Comments:**
> **username_1**: Optimization version of 3D matching is a special case of your problem and approximating 3D matching is APX-complete.  
> **username_0**: Thanks @MohammadAl-Turkistany (you can add it as an answer). Do you see an easy way to get a stronger inapproximability result? I'm not sure if this problem is approximable within a constant factor.  
> **username_2**: Your problem is likely to be as hard as maximum independent set. MIS is hard to approximate in graphs with uniform degree and MIS can be reduced to set packing. Putting the two together should give the result.  
> **username_0**: @ChandraChekuri, thanks for your response.  I'm not sure about approximability hardness, but it seems that this problem is $FPT$ while IS is $W[1]-complete$ (see my answer below).  

---

## 2 answers

### Answer by username_0 on 2014-03-18. Score: 1

Not exactly what I was asking for, but I've noticed that this problem is $FPT$ with respect to $k$ (while Set Packing seems to be $W[1]-hard$ with respect to the required number of sets alone (i.e. without bound on the set sizes)).

The algorithm utilizes the famous [color coding](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCcQFjAA&url=http://www.tau.ac.il/~nogaa/PDFS/col5.pdf&ei=_sooU7eACqmY4wTk0IDoDg&usg=AFQjCNH3yxDvNfSlKUXUNL9ZgZ38Mu6emg&sig2=r4wfkYm-o22WObADUNYPjg&bvm=bv.62922401,d.bGQ) scheme in the following way:

-Notice that we can assume w.l.o.g that all set sizes are at most $k-1$ (otherwise we can select the single largest set).

1. "Guess" (i.e. go over all possibilities) the number of elements in the minimal feasible disjoint cover, $x$. Since the sets are of size $\leq k-1$, the smallest feasible cover is of size $k\leq x \leq 2(k-1)$.
2. Randomly color all items by $x$ colors. Denote the coloring by $C$.
3. Use dynamic programming to figure if if a set $S\subseteq [x]$ of item colors can be obtained by selecting disjoint sets. Formally, each cell in our matrix $A$ will be some subset of $[x]$, our initialization will be $A[\emptyset]=true$, and our computation will be $A[t]=\vee\_{t'\subset t}\{((A[t']) \wedge (\exists s\in \mathcal{S}:C(s)\cap A[t']=\emptyset)\wedge (t'\cup C(s)=t)\}$. Basically, $A$ is a boolean matrix denoting if some set $t\subset [x]$ of colors is coverable by disjoint sets.

(from this point is basically follows the CC analysis):

Assuming there was a disjoint cover of size $x$, the probability that all of it's elements will be colored by different colors is $\frac{x!}{x^x}\leq e^{-x}$.

This means that if we repeat steps 2,3 for $O(e^x)$ iterations, we will get a coloring such that with high probability we will be able to cover all $x$ colors in the DP procedure.

The total running time will be $O((2e)^{2k}\cdot poly(n,m))\approx O^\*(29.56^k)$.

Using the same method of computing a $k$-perfact hashing family (instead of the random coloring), this result can also be derandomized with an increase factor of $2^{polylogk}$ to the runtime.


---

### Answer by username_1 on 2014-03-09. Score: 1

Optimization version of 3D matching is a special case of your problem. Approximating [Maximum 3D Matching](http://www.nada.kth.se/~viggo/wwwcompendium/node143.html) is $APX$-complete. However, it is approximable within 3/2$+\epsilon $ for any $\epsilon >0$

References:

Hurkens, C. A. J., and Schrijver, A. (1989), On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems,
SIAM J. Disc. Math. 2, 68-72.

Kann, V. (1991), Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. Process. Lett. 37, 27-35.


---

