# Set cover problem satisfying half constraints

Consider a variation of the set cover problem in which we only have to cover some certain amount of elements. Is this problem still NP-hard? I guess yes? Is there a good reference?

• If we have to cover at least $rn$ elements, we can just add $n/r$ elements not in any set to any instance to reduce to the regular set cover problem. Also, the set cover problem is NP-hard to approximate up to any constant, so even if you are told that there exists a solution covering all elements with at most $k$ sets, it's hard to cover $rn$ elements with at most $k$ sets (consider an instance with $1 / r$ copies of the same instance). – Antti Röyskö Feb 17 at 3:57