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

Jain’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 kk-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).