MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.