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. 



How to prove the NP-hardness of this set covering problem
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.


