Improved approximation algorithms for some capacitated $k$ edge connectivity problems
July 04, 2023 Β· Declared Dead Β· π arXiv.org
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β Data Structures & Algorithms
π
π
The Cartographer
R.I.P.
π»
Ghosted
Route Planning in Transportation Networks
R.I.P.
π»
Ghosted
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
R.I.P.
π»
Ghosted
Hierarchical Clustering: Objective Functions and Algorithms
R.I.P.
π»
Ghosted
Graph Isomorphism in Quasipolynomial Time
π
π
The Cartographer
Simulation optimization: A review of algorithms and applications
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted