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.
Set packing with maximum coverage objective
cc.complexity theory;ds.algorithms;complexity classes;approximation algorithms;approximation hardness