Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
From MaRDI portal
Publication:2496319
DOI10.1016/j.jcss.2005.05.006zbMath1103.68139OpenAlexW1968690018MaRDI QIDQ2496319
Publication date: 12 July 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.006
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Improved approximation algorithms for single-tiered relay placement ⋮ Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ On Element-Connectivity Preserving Graph Simplification ⋮ Survivable network activation problems ⋮ Unnamed Item ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ A unified algorithm for degree bounded survivable network design ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Pruning 2-connected graphs ⋮ Approximating node-connectivity augmentation problems ⋮ Degree constrained node-connectivity problems ⋮ Black-box reductions for cost-sharing mechanism design ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Approximability of Capacitated Network Design ⋮ Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Simpler analysis of LP extreme points for traveling salesman and survivable network design problems ⋮ A note on Rooted Survivable Networks ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Relay placement for two-connectivity ⋮ Unnamed Item ⋮ A primal-dual approximation algorithm for the survivable network design problem in hypergraphs ⋮ Approximability of capacitated network design ⋮ Approximation algorithms for connectivity augmentation problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matroids and linking systems
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Design of survivable networks
- Geometric algorithms and combinatorial optimization
- Approximating node connectivity problems via set covers
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- Minimal edge-coverings of pairs of sets
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A primal–dual schema based approximation algorithm for the element connectivity problem
- Improved Approximation Algorithms for Uniform Connectivity Problems
