If you want to make money online : Register now

[Solved]: Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

, , No Comments
Problem Detail: 

I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help.

The Weighted Maximum Coverage problem is formulated as follows (known to be NP-hard):

Given a set I of m elements with each element ej has a weight w(ej), a collection of subsets S=S1,S2,...Sn with each set covers some elements, and an integer k, the object is to find k subsets to maximize the sum weights of covered elements.

Now, my concern is as follows:

When the weight for each element is the number of subsets that cover this element, is the problem still NP-hard? How to prove it?

For example, given I={a,b,c,d}, S=S1,S2,S3, and S1={a,b,c} S2={b,c} S3={c,d}, then the weight of element b is 2, since there are two subset, S1 and S2, covers b.

Asked By : John

Answered By : Yuval Filmus

If you allow sets to repeat, then you can show that this is still NP-hard by making all the weights equal. The idea is to reduce from unweighted maximum coverage to your version of maximum coverage. Given an instance of unweighted maximum coverage, where element $e_i$ appears $w_i$ times, let $W = \max_i w_i$, and for each element $e_i$ of non-zero weight, add $W-w_i$ sets of the form $\{e_i\}$. In the new instance, each element appears the same number of times, so all have the same weight; and one checks that the added sets cannot improve the optimal solution.

If you insist that the sets are disjoint, you repeat the same construction, but to each set in the construction (old and new) you add a unique dummy element. This increases the value of each feasible solution by exactly $k$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32678

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback