In the {\it smallest $k$-ECSS problem} we are given a graph and an integer $k$; we seek a $k$-edge connected spanning subgraph that contains the fewest possible number of edges. We prove a tight bound on the performance of the simplest and most natural approximation algorithm based on LP-rounding. The bound on the approximation ratio is $1+2/k$ for directed graphs or undirected graphs with $k$ even, and $1+3/k$ for undirected graphs with $k>1$ odd. Iterated rounding improves the last upper bound to $1+2/k$. These results demonstrate a phenomenon that was suspected from previous work, that the smallest $k$-ECSS problem gets easier to approximate as $k$ tends to infinity. Our second algorithm is the directed version of Jain's iterated rounding approach to network design. The problem is to approximate a minimum cost set of directed edges that cover a crossing supermodular function. We show that iterated rounding gives a factor 3 approximation, where factor 4 was previously known and factor 2 was conjectured. Our bound is tight for the simplest interpretation of iterated rounding. We also discuss iterated rounding on mixed graphs, showing the approximation ratio is unbounded.

The first part of the talk is joint work with Michel Goemans, Eva Tardos and David Williamson.