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.

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.