<ol>
<li><p>Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a corresponding subset $S_v$ in your set system that contains the (closed) neighborhood of $v$. Then finding a cardinality-$k$ independent set in $G$ is equivalent to finding a cardinality-$k$ sub-system of disjoint sets in your set system. 
"Independent Set" cannot be approximated in polynomial time within a factor of $|V|^{1-\varepsilon}$ for any $\varepsilon&gt;0$, unless P=NP.</p></li>
<li><p>Your second problem is known as "Maximum k-Coverage". It is APX-complete (and hence does not allow a PTAS), but has a (poly-time) constant factor approximation algorithm due to Hochbaum and Pathria:</p></li>
</ol>

<p>Hochbaum, D. S. and Pathria, A. (1998), Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics 45: 615–627. </p>

<p><a href="http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291520-6750%28199809%2945:6%3C615::AID-NAV5%3E3.0.CO;2-5/abstract" rel="nofollow">link to Hochbaum &amp; Pathria paper</a></p>

CC BY-SA 3.0
2015-01-12T16:02:41.147Z
2015-01-12T16:02:41.147Z
Gamow
<p>Problem 1 is known as <a href="http://en.wikipedia.org/wiki/Set_packing" rel="nofollow">SET PACKING</a>. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard. </p>

CC BY-SA 3.0
2014-03-05T17:44:29.647Z
2014-03-05T17:44:29.647Z
Suresh Venkat
<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>I'm interested in the approximability of two problems, or in general, what is known about them.</p>

<ol>
<li>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.</li>
<li>Given a number $k''\in[n]$, 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.</li>
</ol>

<hr>

<ul>
<li>The problems are NP-complete:
The first has a straight forward reduction from 3-dimensional matching, and the second answers exact cover directly.</li>
<li>
The first problem seems $APX-hard$ if we use the hardness results from <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.7104&amp;rep=rep1&amp;type=pdf" rel="nofollow">k-dimensional matching</a>. </li>
<li>Both problems can be viewed as a special case of Independent Set over the graph whose vertices are $\mathcal{S}$ and there's an edge $(s_i,s_j)$ iff $s_i\cap s_j$ isn't empty ( (2) has vertices weights $w(s_i)=|s_i|$), but I don't see any easy reduction from $IS$ to either that doesn't require exponential size blowup.</li>
</ul>

<p><strong>What can we say about the approximability of the two problems? maximal</strong> <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.7104&amp;rep=rep1&amp;type=pdf" rel="nofollow">k-dimensional matching</a> <strong>is known to be approximable within a factor of $\frac{k}{2}$, does it have an analogue for the first problem?</strong> </p>

<p>Both of these problems seems natural, so I'm tagging this question as a reference request, assuming they have been looked at under different name, rings a bell to anyone?</p>

CC BY-SA 3.0
2014-03-05T21:44:20.017Z
There is an easy reduction from IS to Set Packing. For each vertex $v$ create a set $S_v$ which contains all the edges incident to $v$ as its elements.
Chandra Chekuri
<reference-request><approximation-algorithms><set-cover><exact-cover><covering-problems>
Covering by disjoint sets
R B
# Covering by disjoint sets

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

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}$.

I'm interested in the approximability of two problems, or in general, what is known about them.

1. 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.
2. Given a number $k''\in[n]$, 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.

---

* The problems are NP-complete:
  The first has a straight forward reduction from 3-dimensional matching, and the second answers exact cover directly.
* The first problem seems $APX-hard$ if we use the hardness results from [k-dimensional matching](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.7104&rep=rep1&type=pdf).
* Both problems can be viewed as a special case of Independent Set over the graph whose vertices are $\mathcal{S}$ and there's an edge $(s\_i,s\_j)$ iff $s\_i\cap s\_j$ isn't empty ( (2) has vertices weights $w(s\_i)=|s\_i|$), but I don't see any easy reduction from $IS$ to either that doesn't require exponential size blowup.

**What can we say about the approximability of the two problems? maximal** [k-dimensional matching](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.7104&rep=rep1&type=pdf) **is known to be approximable within a factor of $\frac{k}{2}$, does it have an analogue for the first problem?**

Both of these problems seems natural, so I'm tagging this question as a reference request, assuming they have been looked at under different name, rings a bell to anyone?

**Tags:** reference-request, approximation-algorithms, set-cover, exact-cover, covering-problems

> **Comments:**
> **username_1**: There is an easy reduction from IS to Set Packing. For each vertex $v$ create a set $S_v$ which contains all the edges incident to $v$ as its elements.  

---

## 2 answers

### Answer by username_2 on 2015-01-12. Score: 1 | Accepted answer

1. Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a corresponding subset $S\_v$ in your set system that contains the (closed) neighborhood of $v$. Then finding a cardinality-$k$ independent set in $G$ is equivalent to finding a cardinality-$k$ sub-system of disjoint sets in your set system.
   "Independent Set" cannot be approximated in polynomial time within a factor of $|V|^{1-\varepsilon}$ for any $\varepsilon>0$, unless P=NP.
2. Your second problem is known as "Maximum k-Coverage". It is APX-complete (and hence does not allow a PTAS), but has a (poly-time) constant factor approximation algorithm due to Hochbaum and Pathria:

Hochbaum, D. S. and Pathria, A. (1998), Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics 45: 615–627.

[link to Hochbaum & Pathria paper](http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291520-6750%28199809%2945:6%3C615::AID-NAV5%3E3.0.CO;2-5/abstract)


---

### Answer by username_3 on 2014-03-05. Score: 1

Problem 1 is known as [SET PACKING](http://en.wikipedia.org/wiki/Set_packing). Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.


---

