Set packing with maximum coverage objective

Question

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.

• Mohammad Al-Turkistany: Optimization version of 3D matching is a special case of your problem and approximating 3D matching is APX-complete.
• R B: 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.
• Chandra Chekuri: 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.
• R B: @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).

Answer 1

Optimization version of 3D matching is a special case of your problem. Approximating Maximum 3D Matching 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.

Answer 2

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