Maximum Positive Negative Set Cover Problem I am considering the following problem. 

Input: Given two disjoint subsets $A$ and $B$ and a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq A \cup B$ for all $i=1\ldots k$.

Solution form: A collection $C' \subseteq C$.

Objective: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| + \left|B \setminus\left(\bigcup\limits_{c \in C'} c\right)\right|$.

That is, maximize the nodes in A covered plus the nodes in B not covered.

I am wondering the hardness of approximation.

Related work:

If we consider minimizing the objective, it becomes the problem studied in the following paper.

Miettinen, Pauli. "On the positive–negative partial set cover problem." Information Processing Letters 108.4 (2008): 219-221
This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $C' \in \{\emptyset, C\}$ with a higher objective score.

Here's a loose constant-factor hardness result. No significant effort was put into optimizing the constant. I'm sure others can find something tighter.



Let $G = (V,E)$ be an instance of Max-Cut. We construct $A$, $B$, and $C$ as follows:


$A$ contains two vertices, $a_{u,v}$ and $a_{v,u}$, for each $(u,v) \in E$.
$B$ contains two vertices, $b_{u,v}$ and $b_{v,u}$, for each $(u,v) \in E$.
$C$ contains one set $c_v$ for each $v \in V$. 
$c_v := \bigcup_{u \in \mathcal{N}(v)} \{a_{u,v}, a_{v,u}, b_{u,v}\}$, where $\mathcal{N}(v)$ denotes the neighborhood of $v$ in $E$.


Every subset of $C$ naturally corresponds to a collection of vertices from $V$ (i.e. via the subscripts). Call the set of vertices in this solution $V_C$.

Now for every edge $(u,v) \in E$, we count how many vertices from $\{a_{u,v}, a_{v,u}, b_{u,v}, b_{v,u}\}$ belong to $S = \left(A\cap \left(\bigcup_{c \in C} c\right)\right) \cup \left(B \setminus \left(\bigcup_{c \in C} c\right)\right)$.


If $u \in V_C$ and $v \in V_C$, then only $a_{u,v}$ and $a_{v,u}$ are in $S$.
If $u \in V_C$ and $v \not\in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{u,v}$ are in $S$.
If $u \not\in V_C$ and $v \in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{v,u}$ are in $S$.
If $u \not\in V_C$ and $v\not\in V_C$, then only $b_{v,u}$ and $b_{u,v}$ are in $S$.


Therefore, the total number of vertices in $S$ is equal to $2|E| + |\textrm{Cut}_E(V_C, V \setminus V_C)|$. Thus, the optimal solution involves a Max-Cut computation.

If it is hard to distinguish Max-Cut instances with optimal value $\geq \alpha |E|$ from those with value $\leq \beta |E|$, then for your problem it's hard to distinguish instances with optimal value $\geq (2+\alpha)|E|$ from those with value $\leq (2+\beta)|E|$, for a hardness of $\frac{2 + \beta}{2 + \alpha} = 1 - \frac{\alpha - \beta}{2 + \alpha} &lt; 1 - (\alpha - \beta)/3$. 

At this point we can plug in our favorite result on the hardness of max cut. E.g. UGC implies that we can choose $\alpha - \beta &gt; .1$,$^*$ so this gives us a UGC gap of something less than $1-(1/10)/3 = 29/30$. Similar results can be had for NP-hardness, albeit with a slightly bigger constant.

$^*$ Note: this is not quite $1-\alpha_{GW}$, since $\alpha_{GW}$ measures the gap ratio rather than the gap difference.