AN O(log(2) k)-APPROXIMATION ALGORITHM FOR THE k-VERTEX CONNECTED SPANNING SUBGRAPH PROBLEM

作者：Fakcharoenphol Jittat^*; Laekhanukit Bundit

来源：SIAM Journal on Computing, 2012, 41(5): 1095-1109.

DOI：10.1137/110855910

• approximation algorithm
• network design
• vertex-connectivity
• k-connected graph

We present an O(log(2) k)-approximation algorithm for the problem of finding a k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in an input graph, and k is a connectivity requirement. Our algorithm is the first that achieves a polylogarithmic approximation ratio for all values of k and n, and it works for both directed and undirected graphs. As in previous works, we use the Frank-Tardos algorithm for finding k-outconnected subgraphs as a subroutine. However, with our structural lemmas, we are able to show that we need only partial solutions returned by the Frank-Tardos algorithm; thus, we can avoid paying the whole cost of an optimal solution every time the algorithm is applied.

• 出版日期2012