Bifamily Edge Cover Activation

• INSTANCE: Graph $G=(V,E)$ , monotone activation functions $f_e\colon \mathbb{R}^+\times\mathbb{R}^+\to\{0,1\}$ for the edges $e\in E$ , bifamily ${\mathcal F}$ of subsets of $V$
• SOLUTION: assignment $x=(x_v)_{v\in V}\in \mathbb{R}^{\vert V\vert}$ such that the set $E_x$ of activated edges $e=\{u,v\}$ (i.e. $f_e(x_u,x_v)=1$ ) covers ${\mathcal F}$
• COST FUNCTION: $\sum_{v\in V}x_v$
• OBJECTIVE: Minimize
• Approx.: Admits an $O(\log \vert{\mathcal C}_{{\mathcal F}}\vert)$ -approximation algorithm for the case when ${\mathcal F}$ is an uncrossable family, where ${\mathcal C}_{{\mathcal F}}$ is the set of all subsets $X$ for which $\hat{X}\in {\mathcal F}$ and $X$ does not contain two distinct inclusion-minimal members of the family $\{X\vert\hat{X}\in {\mathcal F}\}$ [92]
• Comment: A bifamily ${\mathcal F}$ of subsets of $V$ is a set of pairs $\hat{X}=(X,X^+)$ of subsets of $V$ such that for each $\hat{X}=(X,X^+)$ , $X\subseteq X^+$ and the following property holds: For all $\hat{X}=(X,X^+)$ and $\hat{Y}=(Y,Y^+)$ in ${\mathcal F}$ , $X=Y$ implies $X^+=Y^+$ and $X\subseteq Y$ implies $X^+\subseteq Y^+$ . A set of edges $E'\subseteq E$ covers ${\mathcal F}$ if for each $\hat{X}=(X,X^+)$ in ${\mathcal F}$ , there is an edge $e\in E'$ which goes from $V\setminus X^+$ to $X$ .