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:
- Can we do better on this special instances?
- Is there a known inapproximability result for this kind of problem?
- Does this problem has a name in the literature?
- 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\}$