Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano
  • Iterated Rounding Algorithm...
    Gabow, Harold N.; Gallagher, Suzanne R.

    SIAM journal on computing, 01/2012, Letnik: 41, Številka: 1
    Journal Article

    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^2})$. The more precise version of this bound requires $k\ge 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\sqrt 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 $\le 1+c/k$ implies $P=NP$. Our approximation ratio extends to the minimum-size Steiner network problem, where $k$ denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding.