Improved approximation algorithms for some capacitated $k$ edge connectivity problems

July 04, 2023 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Zeev Nutov arXiv ID 2307.01650 Category cs.DS: Data Structures & Algorithms Citations 6 Venue arXiv.org Last Checked 4 months ago
Abstract
We consider the following two variants of the Capacitated $k$-Edge Connected Subgraph} (Cap-k-ECS) problem. Near Min-Cuts Cover: Given a graph $G=(V,E)$ with edge costs and $E_0 \subseteq E$, find a min-cost edge set $J \subseteq E \setminus E_0$ that covers all cuts with at most $k-1$ edges of the graph $G_0=(V,E_0)$. We obtain approximation ratio $k-Ξ»_0+1+Ξ΅$, improving the ratio $2\min\{k-Ξ»_0,8\}$ of Bansal, Cheriyan, Grout, and Ibrahimpur for $k-Ξ»_0 \leq 14$,where $Ξ»_0$ is the edge connectivity of $G_0$. $(k,q)$-Flexible Graph Connectivity ($(k,q)$-FGC): Given a graph $G=(V,E)$ with edge costs and a set $U \subseteq E$ of ''unsafe'' edges and integers $k,q$, find a min-cost subgraph $H$ of $G$ such that every cut of $H$ has at least $k$ safe edges or at least $k+q$ edges. We show that $(k,1)$-FGC admits approximation ratio $3.5+Ξ΅$ if $k$ is odd (improving the previous ratio $4$), and that $(k,2)$-FGC admits approximation ratio $6$ if $k$ is even and $7+Ξ΅$ if $k$ is odd (improving the previous ratio $20$).
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted