# complexity theory – Is this variation of Max-Coverage NP-hard?

Setup

An instance of Max-Coverage is typically defined by a collection of $$n$$ sets $$S = {s_1, s_2, dots, s_n}$$, and a budget $$k$$, where the objective is to select a subset $$Usubset S$$ such that
$$big|Ubig| leq k,~text{ and }~big|cup_{sin U}sbig|~text{ is maximized}.$$

The variation I am interested in is as follows. Instead of being given a collection of sets, we are given a collection of $$n$$ pairs of sets, $$S = big{p_1 ={s_{1, 0}, s_{1, 1}}, p_2={s_{2, 0}, s_{2, 1}}, dots, p_n={s_{n, 0}, s_{n, 1}}big}$$. Further, instead of selecting $$k$$ sets, we now have to select one set from each pair of sets say $$U = { s_{1, i_1}, s_{2, i_2}, dots s_{n, i_n}}$$ s.t. $$i_jin{0, 1}$$ and
$$big|cup_{sin U}sbig|~text{ is maximized}.$$

Questions

1.] Is it NP-hard to optimally select one set from each pair such their union is maximized?

2.] Let $$A$$ be the universe of possible set elements and for each $$i leq n$$, we have $$s_{i, 0} cup s_{i, 1} = A$$ and $$s_{i, 0} cap s_{i, 1} = emptyset$$.

Posted on Categories Articles