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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.