A bad example for the iterative rounding method for mincost k-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 k-connected spanning subgraph problem, but the approximation guarantees given by the method are weak. We construct a family of examples such that the standard LP relaxation has an extreme point solution with infinity norm (1) / p k, thus showing that the standard iterative rounding method cannot achieve an approximation guarantee better than ( p k).