Approximating minimum-cost edge-covers of crossing biset-families
type: Item
instance of: scholarly article
title: Approximating minimum-cost edge-covers of crossing biset-families
zbMATH Open document ID: 1313.05208
author: Zeev Nutov
published in: Combinatorica
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1207.4366
review text: Let \(V\) be a set. Then, a pair \((S,S^{+})\) of subsets of \(V\) with \(S\subseteq S^{+}\) is a biset on \(V\). A family \(\mathcal F\) of bisets on a set \(V\) is crossing if \((X\cap Y,X^{+}\cap Y^{+}),(X\cup Y,X^{+}\cup Y^{+})\in\mathcal F\) for all \((X,X^{+}),(Y,Y^{+})\in \mathcal F\) with \(X\cap Y\neq\emptyset\) and \(X^{+}\cup Y^{+}\neq V\), \(\mathcal F\) is \(k\)-regular if \((X\cap Y,X^{+}\cap Y^{+}),(X\cup Y,X^{+}\cup Y^{+})\in \mathcal F\) for all \((X,X^{+}),(Y,Y^{+})\in\mathcal F\) with \(X\cap Y\neq\emptyset\) and \(| V\setminus (X\cup Y)| \geq k+1\). For a family \( \mathcal F\) of bisets on \(V\) the family \(\{(V\setminus S^{+},V\setminus S)\mid (S,S^{+})\in \mathcal F \}\) is a co-family of \(\mathcal F\). A directed edge \((x,y)\) covers a biset \((S,S^{+})\) if \(x\in S\) and \(y\in V\setminus S^{+}\). A biset-family edge-cover problem is: for a given directed graph \((V,E)\), a cost function \(c:E\to \mathbb R\) and a family \(\mathcal F\) of bisets on \(V\) find a minimum cost set \(J\subseteq E\) such that every biset in \(\mathcal F\) is covered by an edge from \(J\). The paper presents an \(O(\log| V|)\)-approximation polynomial time algorithm solving the biset-family edge-cover problem for crossing families of bisets. Moreover, if both \(\mathcal F\) and the co-family of \(\mathcal F\) are \(k\)-regular and \(| S^{+}\setminus S| =k\) for every \((S,S^{+})\in \mathcal F\) then the ratio of the algorithm is \(O(\log\frac {| V| }{| V| -k})\). Some consequences for other network problems -- e.g. for the \(k\)-connected subgraph problem, the subset \(k\)-connected subgraph problem etc. -- are derived and discussed. Finally, some open problem are formulated and discussed.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6330532
zbMATH Keywords: family of bisets
zbMATH Keywords: approximation algoritm
zbMATH Keywords: network problem
zbMATH Keywords: connectivity
MaRDI profile type: Publication
OpenAlex ID: W2033691165
arXiv ID: 1207.4366
cites work: A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
cites work: Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
cites work: An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
cites work: Q3549695
cites work: Rooted \(k\)-connections in digraphs
cites work: Minimal edge-coverings of pairs of sets
cites work: On the optimal vertex-connectivity augmentation
cites work: Hardness of Approximation for Vertex-Connectivity Network Design Problems
cites work: Approximating k-node Connected Subgraphs via Critical Graphs
cites work: An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
cites work: Inapproximability of survivable networks
cites work: Approximating Subset k-Connectivity Problems
cites work: An approximation algorithm for minimum-cost vertex-connectivity problems
cites work: Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
DOI: 10.1007/S00493-014-2773-4
description: scientific article