Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

DOI10.1016/j.jcss.2005.05.006zbMath1103.68139OpenAlexW1968690018MaRDI QIDQ2496319

Yanyan Li

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

zbMATH Keywords

approximation algorithmnetwork design

Mathematics Subject Classification ID

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