The classic Maximum Coverage (MC) problem is an NP-hard optimization problem. Consider d elements U = {e1, e2, ... ed} and c sets T1, T2 ... Tc. Each set contains some elements in U. The problem aims to find at most b sets, such that the cardinality of the union of these sets is maximized. For example, T1={e1, e3}, T2={e1, e2, e3} and T3={e3, e4}. When b=2, the optimal solution picks T2 and T3. I am considering a variation of the classic MC problem, which imposes a set size constraint. Consider 1 < k <= d, if the size of all sets is bounded by k. Call this problem k-MC. Is the problem still NP-hard?
My conjecture is that k-MC is still NP-hard, but I am struggling to come up with a polynomial reduction from a proven NP-hard problem, like MC. For an arbitrary instance of Maximum coverage, if I could find a polynomial reduction to my problem for all k>1, I can conclude that my problem is also NP-hard. Here is what I got so far:
- When k=d, the problem is trivially equivalent to the classic Maximum Coverage.
- When k=d-1, we look at the given MC instance and see if there exist a set with size d. If there is, simply pick that. Otherwise, it reduces to the k-MC problem with k=d-1.
When k is less than d-1, I resort to dynamic programming to complete the reduction. However, this yields a non-polynomial time reduction, which defeat the purpose of reduction from a NP-hard problem.
If anyone could give me some pointers on how I should tackle this problem, or even just make an educated guess on the problem complexity of k-MC (P or NP), I'd really appreciate it.