Maximum Coverage Problem is NP-hard, it goes like this:
Having $n$ sets $A = \{a_1, a_2, \dots, a_n\}$, choose at most $k$ of them, in such a way, that their union will be as big as possible. $$\max\limits_{B \in 2^\mathit{A}} \bigcup\limits_{b \in B}b\text{ s.t. } \big| B\big| \leq k$$ I have an opposite problem, let me call it Minimum Coverage Problem:
Having $n$ sets $A = \{a_1, a_2, \dots, a_n\}$, choose at least $k$ of them, in such a way, that their union will be as small as possible.
$$\min\limits_{B \in 2^\mathit{A}} \bigcup\limits_{b \in B}b\text{ s.t. } \big| B\big| \geq k$$
Is this problem still NP-hard? If so - why? And if not - how could it be solved?