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