An ordered pair $\hat{ S}=(S,S^+)$ of subsets of $V$ is called a { \em biset} if $S \subseteq S^+$; $(V-S^+,V-S)$ is the co-biset of $\hat{ S}$. Two bisets $\hat{ X},\hat{ Y}$ intersect if $X \cap Y \neq \emptyset$ and cross if both $X \cap Y \neq \emptyset$ and $X^+ \cup Y^+ \neq V$. The intersection and the union of two bisets $\hat{ X},\hat{ Y}$ is defined by $\hat{ X} \cap \hat{ Y} = (X \cap Y, X^+ \cap Y^+)$ and $\hat{ X} \cup \hat{ Y} = (X \cup Y,X^+ \cup Y^+)$. A biset-family ${ \cal F}$ is crossing (intersecting) if $\hat{ X} \cap \hat{ Y}, \hat{ X} \cup \hat{ Y} \in { \cal F}$ for any $\hat{ X},\hat{ Y} \in { \cal F}$ that cross (intersect). A directed edge covers a biset $\hat{ S}$ if it goes from $S$ to $V-S^+$. We consider the problem of covering a crossing biset-family ${ \cal F}$ by a minimum-cost set of directed edges. While for intersecting ${ \cal F}$, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing ${ \cal F}$ is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently. Let us say that a biset-family ${ \cal F}$ is $k$-regular if $\hat{ X} \cap \hat{ Y}, \hat{ X} \cup \hat{ Y} \in { \cal F}$ for any $\hat{ X},\hat{ Y} \in { \cal F}$ with $|V-(X \cup Y)| \geq k+1$ that intersect. In this paper we obtain an $O(\log |V|)$-approximation algorithm for arbitrary crossing ${ \cal F}$; if in addition both ${ \cal F}$ and the family of co-bisets of ${ \cal F}$ are $k$-regular, our ratios are: $O(\log \frac{ |V|}{ |V|-k})$ if $|S^+ \setminus S|=k$ for all $\hat{ S} \in { \cal F}$, and $O(\frac{ |V|}{ |V|-k} \log \frac{ |V|}{ |V|-k})$ if $|S^+ \setminus S| \leq k$ for all $\hat{ S} \in { \cal F}$. Using these generic algorithms, we derive approximation algorithms for some network design problems.
Categories: cs.DS