<p>Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem?</p>

<p>The general Set Packing Problem would be:
Given A Collection of Sets $S=\{S_1,\ldots,S_n\}$ over a base set $U$, find the subset $S&#39;\subseteq S$ such that each element of $U$ is covered at most once (i.e. the sets in $S&#39;$ are mutually disjoint) and $S&#39;$ has the maximum total weight over all such subsets. </p>

<p>And my weight function assigns a set $S_i$ the weight $|S_i-1|$</p>

<p>Then, the IP would be</p>

<p>$\max \sum_{S_i \in S}|S_i-1|x_{S_i}$</p>

<p>s.t. $\sum_{S_i:c\in S_i}x_{S_i}\leq 1 \hspace{1 cm} \forall c\in U$</p>

<p>$x_{S_i}\in\{0,1\}$</p>

<p>It is easy to see that the problem is NP-complete, by reducing Exact Cover by 3-Sets on it. 
All approximation algorithms from the classical weighted set packing problem obviously work here as well.</p>

<p>My Questions: </p>

<ol>
<li>Can we do better on this special instances?</li>
<li>Is there a known inapproximability result for this kind of problem?</li>
<li>Does this problem has a name in the literature?</li>
<li>What about the following minimization version: Cover as many elements as possible with the least number of sets? More specific: We have that the sets in $S$ contain also the singleton sets $\{c\}$ for all $c\in U$. That is, we can easily generate a feasible solution. And we want to find the solution to the following IP:</li>
</ol>

<p>$\min \sum_{S_i \in S}x_{S_i}$</p>

<p>s.t. $\sum_{S_i:c\in S_i}x_{S_i}= 1 \hspace{1 cm} \forall c\in U$</p>

<p>$x_{S_i}\in\{0,1\}$</p>

CC BY-SA 3.0
2012-02-15T19:53:43.570Z
The hardness of set packing comes is via a reduction from the maximum independent set problem; the sets correspond to the nodes and the elements correspond to the edges of the graph. Independent set hardness results hold for almost regular graphs so the corresponding set packing problem would have sets of roughly equal size if not exactly equal. Therefore the special case you have does not really help. This is a some what informal comment so you need to look at the specific hardness results for maximum independent set to figure out the details. Your last question is not well-defined.
Chandra Chekuri
CC BY-SA 3.0
2012-02-16T09:21:47.797Z
Thank your for your comment. I will look into the details of the proofs and have (hopefully) clarified the last question. Any further comments appreciated.
Neele
CC BY-SA 3.0
2012-02-16T14:37:41.737Z
Thanks to your comment, I found a paper by Hazan et al (2006), which states that maximum k-set packing is not efficiently approximable within $\Omega(\frac{k}{\ln(k)})$ unless P=NP. Since for uniformly sized sets set packing equals my problem, if I conclude correctly, this means that my problem does at least not have any constant approximation factor.
Neele
CC BY-SA 3.0
2012-02-17T15:09:58.810Z
As Chandra Chekuri pointed out, “Cover as many elements as possible with the least number of sets” is not well-defined, because it contains two objective functions which cannot be optimized simultaneously in general.  In particular, that description does not match your integer-programming formulation.
Tsuyoshi Ito
<cc.complexity-theory><approximation-algorithms><approximation-hardness><set-cover><packing>
Hardness of Approximation results for Special Set Packing Problem Wanted
Neele
# Hardness of Approximation results for Special Set Packing Problem Wanted

(Asked by: username_0 on 2012-02-15)

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem?

The general Set Packing Problem would be:
Given A Collection of Sets $S=\{S\_1,\ldots,S\_n\}$ over a base set $U$, find the subset $S'\subseteq S$ such that each element of $U$ is covered at most once (i.e. the sets in $S'$ are mutually disjoint) and $S'$ has the maximum total weight over all such subsets.

And my weight function assigns a set $S\_i$ the weight $|S\_i-1|$

Then, the IP would be

$\max \sum\_{S\_i \in S}|S\_i-1|x\_{S\_i}$

s.t. $\sum\_{S\_i:c\in S\_i}x\_{S\_i}\leq 1 \hspace{1 cm} \forall c\in U$

$x\_{S\_i}\in\{0,1\}$

It is easy to see that the problem is NP-complete, by reducing Exact Cover by 3-Sets on it.
All approximation algorithms from the classical weighted set packing problem obviously work here as well.

My Questions:

1. Can we do better on this special instances?
2. Is there a known inapproximability result for this kind of problem?
3. Does this problem has a name in the literature?
4. What about the following minimization version: Cover as many elements as possible with the least number of sets? More specific: We have that the sets in $S$ contain also the singleton sets $\{c\}$ for all $c\in U$. That is, we can easily generate a feasible solution. And we want to find the solution to the following IP:

$\min \sum\_{S\_i \in S}x\_{S\_i}$

s.t. $\sum\_{S\_i:c\in S\_i}x\_{S\_i}= 1 \hspace{1 cm} \forall c\in U$

$x\_{S\_i}\in\{0,1\}$

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, set-cover, packing

> **Comments:**
> **username_1**: The hardness of set packing comes is via a reduction from the maximum independent set problem; the sets correspond to the nodes and the elements correspond to the edges of the graph. Independent set hardness results hold for almost regular graphs so the corresponding set packing problem would have sets of roughly equal size if not exactly equal. Therefore the special case you have does not really help. This is a some what informal comment so you need to look at the specific hardness results for maximum independent set to figure out the details. Your last question is not well-defined.  
> **username_0**: Thank your for your comment. I will look into the details of the proofs and have (hopefully) clarified the last question. Any further comments appreciated.  
> **username_0**: Thanks to your comment, I found a paper by Hazan et al (2006), which states that maximum k-set packing is not efficiently approximable within $\Omega(\frac{k}{\ln(k)})$ unless P=NP. Since for uniformly sized sets set packing equals my problem, if I conclude correctly, this means that my problem does at least not have any constant approximation factor.  
> **username_2**: As username_1 pointed out, “Cover as many elements as possible with the least number of sets” is not well-defined, because it contains two objective functions which cannot be optimized simultaneously in general.  In particular, that description does not match your integer-programming formulation.  

---

## 0 answers

