Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity
\begin{equation}
\sum_{k=1}^m\left\lvert\bigcup_{i=1}^k S_{\pi(i)} \right\rvert.
\end{equation}
This problem is NPcomplete as it contains Exact cover by 3sets as a special case: Suppose $n$ is divisible by 3, say $n=3n'$, and all sets $S_i$ have size 3. Then the upper bound
\begin{equation}
3(1+2+\cdots+n')+(mn')n
\end{equation}
can be achieved if and only if $U$ can be covered by $n'$ of the 3sets. I'm interested in the hardness of approximation. For instance, can the hardness of approximation for set cover be used to say something about the above problem?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


