1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Arnaud
    Commented Oct 7, 2013 at 11:02
  • $\begingroup$ @Arnaud Thanks! I have re-defined the problem. Hope it is clear now. $\endgroup$
    – Fnatic
    Commented Oct 7, 2013 at 11:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .