# Approximation for accumulative set cover

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 $$\sum_{k=1}^m\left\lvert\bigcup_{i=1}^k S_{\pi(i)} \right\rvert.$$ 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 $$3(1+2+\cdots+n')+(m-n')n$$
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?

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