1

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.

Fnatic
  • 23
  • 4
  • You will probably have to make the statement of your "modified set covering" problem more precise. For example, what is the cost of $A$ if I choose all three of $A$, $B$, and $C$? Exactly how is the cost of a set determined? – user642796 Oct 07 '13 at 10:24
  • @ArthurFischer Thanks! I have revised the title and statement of the problem. Hope this time it is clear. – Fnatic Oct 07 '13 at 11:24

1 Answers1

0

You can prove a problem is NP-hard by showing a polynomial time reduction of a known NP-hard problem to your problem. Observe that SET COVER can be reduced to your problem by padding out all the sets with duplicate elements so that they all have the same cardinality, which can be done in polynomial time. This is a polynomial many-one reduction from SET COVER to your problem, which proves that your problem is NP-hard.

Kyle Jones
  • 1,871