7
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Feb 15 '12 at 19:53
  • $\begingroup$ 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. $\endgroup$ – Neele Feb 16 '12 at 9:21
  • $\begingroup$ 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. $\endgroup$ – Neele Feb 16 '12 at 14:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 17 '12 at 15:09

Your Answer

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

Browse other questions tagged or ask your own question.