Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a minimum cost subcollection of $S$ that covers all elements in $U$. It is well known that the Set Covering problem is NP-hard.

Now my question is: Is the problem of finding a subcollection $A$ of $S$ that covers all elements in $U$ with minimum $\sum\limits_{i=1}^{|A|} |s_i| \cdot i$ (Here $|A|$ denotes the number of subsets in subcollection $A$, and $|s_i|$ denotes the number of elements in subset $s_i$. A is sorted in non-increasing order of $|s_i|$) still NP-hard. If so, how to prove it? Thanks in advance.

share|improve this question
    
This seems quite ill-defined to me. It looks like for any choice of a subcollection, there is a cost function $f(A_1 \ldots A_k)$. But what does "not known in advance" mean ? NP-hardness does not make sense in an online setting. On the other hand, if the function f is known beforehand, is it fixed or part of the input ? In the latter case, specializing $f(A_1 \ldots A_k)=k$ reduces it back to the usual covering problem. In the former, some instances will be trivial (take f=0 for example). Do you want to determine which properties of f will make it hard ? –  Arnaud Oct 7 '13 at 11:02
    
@Arnaud Thanks! I have re-defined the problem. Hope it is clear now. –  Fnatic Oct 7 '13 at 11:26

1 Answer 1

up vote 1 down vote accepted

Yes, it is still NP-Hard. First, note that the unweighted set cover problem is also NP-hard. We can reduce the unweighted set cover problem $(U,S)$ to your problem as follows.

First, constructing a new ground set $U'=U\cup V\cup \{x\}$, where $|V|=|U|=n$. Then, extend each set $s_i\in S$ by setting $s_i'=s_i\cup V_i$ where $V_i$ is some subset of $V$ containing $n-|s_i|$ elements, so that each $s_i'$ has $n$ elements. Finally add one last set $s_0'=V\cup \{x\}$ so that $S'=\{s_0',s_1',\ldots,s_m'\}$.

The solution to your version of the set cover problem with $S'$ and $U'$ will return $s_0'$ along with an optimal solution to the original unweighted set cover problem -- since all the sets in $S'$ are of equal size, then the weighting scheme won't matter.

share|improve this answer
    
Thanks, mpg, that is the right answer i want. –  Fnatic Oct 8 '13 at 7:31

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.