Network design via iterative rounding of setpair relaxations
From MaRDI portal
Publication:858116
DOI10.1007/s00493-006-0016-zzbMath1109.68136OpenAlexW1976459503MaRDI QIDQ858116
Adrian Vetta, Joseph Cheriyan, Santosh Vempala
Publication date: 8 January 2007
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-006-0016-z
Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity, On Element-Connectivity Preserving Graph Simplification, A Spectral Approach to Network Design, Unnamed Item, Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design, A unified algorithm for degree bounded survivable network design, Tight approximation algorithm for connectivity augmentation problems, Degree constrained node-connectivity problems, A \(4+\epsilon\) approximation for \(k\)-connected subgraphs, Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation, Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
