A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs

DOI10.1016/j.disopt.2012.10.002zbMath1258.90057OpenAlexW2163661406MaRDI QIDQ1941534

Bundit Laekhanukit, Ashkan Aazami, Joseph Cheriyan

Publication date: 13 March 2013

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.10.002

zbMATH Keywords

graph connectivityapproximation algorithmsLP relaxationsextreme point solutions\(k\)-connected spanning subgraphsiterative rounding method

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (max. 100)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

This page was built for publication: A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs