1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
0
$\begingroup$

Try 3-hitting set. For your special weight setting, the weights are uniform.

$\endgroup$
1
  • 3
    $\begingroup$ Is this just a guess or something you know works? If it's a guess, it would be better as a comment; if it's something you know works, more detail would be useful. $\endgroup$ – David Richerby Nov 6 '14 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.