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

AbstractJain’s iterative rounding method and its variants give the best approximation guarantees known for many problems in the area of network design. The method has been applied to the mincost k-connected spanning subgraph problem. We construct a family of examples such that the standard LP relaxation has an extreme-point solution with infinity norm ≤Θ(1)/k, thus showing that the standard iterative rounding method cannot achieve an approximation guarantee better than Ω(k)