5
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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|$. (en.wikipedia.org/wiki/Maximum_coverage_problem#Greedy_algorithm) $\endgroup$ – Neal Young Apr 14 '13 at 17:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Apr 15 '13 at 4:44

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.