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

Zeev Nutov

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…