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$ 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$ – Suvrit Mar 30 '13 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 Kalinowski Mar 30 '13 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.