# How to prove the NP-hardness of this modified set covering problem

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.

• 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 7 '13 at 10:24
• @ArthurFischer Thanks! I have revised the title and statement of the problem. Hope this time it is clear. – Fnatic Oct 7 '13 at 11:24