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 NP-complete as it contains Exact cover by 3-sets 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')+(m-n')n
\end{equation}
can be achieved if and only if $U$ can be covered by $n'$ of the 3-sets. 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?
$\begingroup$
$\endgroup$
2
asked Mar 30, 2013 at 5:12
-
$\begingroup$ what is $k$ in the inner sum? if $k=m$, then just pick all the sets and you've maximized the sum. so something must be missing.... $\endgroup$– SuvritCommented Mar 30, 2013 at 18:45
-
$\begingroup$ What I mean is to maximize $\lvert S_{\pi(1)}\rvert+\lvert S_{\pi(1)}\cup S_{\pi(2)}\rvert+\lvert S_{\pi(1)}\cup S_{\pi(2)}\cup S_{\pi(3)}\rvert+\cdots$, i.e. a cover of $U$ is built incrementally, and the objective is the sum of the sizes of all the intermediate partial covers. The interesting part is the initial part of $\pi$ until the sets $S_{\pi(1)},\ldots,S_{\pi(k)}$ cover $U$, after which all the terms in the sum are equal to $n$. $\endgroup$– Thomas KalinowskiCommented Mar 30, 2013 at 19:50
Add a comment
|