Approximating minimum-cost edge-covers of crossing biset-families

An ordered pair $\widehat{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 $\widehat{S}$. Two bisets $\widehat{X},\widehat{Y}$ intersect if $X\cap Y\mathrm{\ne }\mathrm{\varnothing }$ and cross if both $X \cap Y \neq \emptyset$and$X^+ \cup Y^+ \neq V$. The intersection and the union of two bisets $\widehat{X},\widehat{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 $\mathcal{F}$ is crossing (intersecting) if $\hat{X} \cap \hat{Y}, \hat{X} \cup \hat{Y} \in {\cal F}$forany$\hat{X},\hat{Y} \in {\cal F}$ that cross (intersect). A directed edge covers a biset $\widehat{S}$ if it goes from $S$ to $V-S^{+}$. We consider the problem of covering a crossing biset-family ${\cal F}$byaminimum-costsetofdirectededges\mathrm{.}Whileforintersecting${\cal F}$, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing $\mathcal{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 $\mathcal{F}$ is $k$-regular if $\widehat{X}\cap \widehat{Y},\widehat{X}\cup \widehat{Y}\in \mathcal{F}$ for any $\widehat{X},\widehat{Y}\in \mathcal{F}$ with $\mathrm{\mid }V-(X\cup Y)\mathrm{\mid }\ge k+1$ that intersect. In this paper we obtain an $O(\log \mathrm{\mid }V\mathrm{\mid })$-approximation algorithm for arbitrary crossing $\mathcal{F}$; if in addition both $\mathcal{F}$ and the family of co-bisets of $\mathcal{F}$ are $k$-regular, our ratios are: $O(\log \frac{|V|}{|V|-k})$if$|S^+ \setminus S|=k$forall$\hat{S} \in {\cal F}$, and $O(\frac{\mathrm{\mid }V\mathrm{\mid }}{\mathrm{\mid }V\mathrm{\mid }-k}\log \frac{\mathrm{\mid }V\mathrm{\mid }}{\mathrm{\mid }V\mathrm{\mid }-k})$ if $\mathrm{\mid }{S}^{+}\setminus S\mathrm{\mid }\le k$ for all $\widehat{S}\in \mathcal{F}$. Using these generic algorithms, we derive approximation algorithms for some network design problems.