ITERATED ROUNDING ALGORITHMS FOR THE SMALLEST k-EDGE CONNECTED SPANNING SUBGRAPH.

We present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is 1 + 1/(2k) + O(1/k²). The more precise version of this bound requires k ≥7, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], 1 + 2/(k + 1). The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + O(1/k√k)) versus 2n). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is 1+(21/11)k < 1+1.91/k for any k > 1. This improves the previous ratio 1+2/k [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant c >0, an approximation ratio ≤ 1+c/k implies P = NP. Our approximation ratio extends to the minimumsize Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. [ABSTRACT FROM AUTHOR]