# Set cover with rewards

I am dealing with the following problem: Given a universe $$U$$, let $$\mathcal{S}$$ be a family of subsets of $$U$$. Each subset $$S\in\mathcal{S}$$ is associated with a non-negative reward, and each element $$u\in U$$ is associated with a non-negative cost. The task is to find a collection of subsets in $$\mathcal{S}$$ maximizing the difference between the total reward in the collection and the costs of elements covered by the collection.

I conjecture this problem is NP-hard, but so far I failed to prove so. The obvious idea from set cover (assigning -1 to each subset and -infinity to each element) fails due to the non-negativity constraint. I was also attempting to find some reduction from MAXSAT, but also with no success. Does anyone have some hints/ideas? Could this be polynomial after all?

Specifically, construct the bipartite graph $$G=(U, \mathcal S, E)$$ where $$E=\{(u, S)\in U\times\mathcal S : u\in S\}.$$ Make the weight of $$u$$ equal to its cost and the weight of $$S$$ equal to its profit. Then a solution (collection $$C$$ of sets) corresponds to the independent set in $$G$$ formed by the union of $$C$$ (as a set of vertices) and the elements in $$U$$ not covered by any set in $$C$$. Conversely any (maximal) independent set $$I$$ in $$G$$ naturally yields the corresponding solution to your problem (choose the sets in $$I\cap S$$ and the elements in $$U\setminus I$$).
Note that the cost of elements covered by sets in $$C$$ is the total cost of all elements, minus the cost of elements not covered by any set in $$C$$. So the stated objective (profit of sets minus cost of covered elements) equals the weight of the corresponding independent set minus the total weight of all elements in $$U$$. So a maximum-weight independent set in $$G$$ (which can be found in polynomial time as $$G$$ is bipartite) corresponds to an optimal solution to your problem.