<p>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 <em>Exact cover by 3-sets</em> 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}<br>
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? </p>

CC BY-SA 3.0
2013-04-14T17:01:28.337Z
FWIW, the greedy algorithm gives a (1-1/e)-approximation, because, for each k, the greedy algorithm gives a (1-1/e)-approximation algorithm for the maximum-coverage problem of choosing a collection $C$ containing $k$ of the sets to maximize $|\bigcup_{S\in C} S_i|$. (http://en.wikipedia.org/wiki/Maximum_coverage_problem#Greedy_algorithm)
Neal Young
CC BY-SA 3.0
2013-04-15T04:44:17.083Z
Related problems in the literature include "Min-sum set cover" and "Minimum latency set cover". The hardness results in the min-sum set cover paper of Feige, Lovasz and Tetali may have some use for the problem at hand.
Chandra Chekuri
<approximation-algorithms><approximation-hardness>
Approximation for accumulative set cover
Thomas Kalinowski
# Approximation for accumulative set cover

(Asked by: username_0 on 2013-04-14)

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?

**Tags:** approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: FWIW, the greedy algorithm gives a (1-1/e)-approximation, because, for each k, the greedy algorithm gives a (1-1/e)-approximation algorithm for the maximum-coverage problem of choosing a collection $C$ containing $k$ of the sets to maximize $|\bigcup_{S\in C} S_i|$. (http://en.wikipedia.org/wiki/Maximum_coverage_problem#Greedy_algorithm)  
> **username_2**: Related problems in the literature include "Min-sum set cover" and "Minimum latency set cover". The hardness results in the min-sum set cover paper of Feige, Lovasz and Tetali may have some use for the problem at hand.  

---

## 0 answers

