Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies (vol 14, 37, 2018)

摘要

There are two errors in our article "Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies" (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that article, we consider the (undirected) Survivable Network problem. The input consists of a graph G = (V, E) with edge-costs, a set T. V of terminals, and connectivity demands {r(st) 0 : st is an element of D subset of T x T}. The goal is to find a minimum cost subgraph of G that for all st is an element of D contains r(st) pairwise internally disjoint st-paths. We claimed ratios O(k ln k) for rooted demands when the set D of demand pairs form a star, where k = max(st is an element of D) r(st) is the maximum demand. This ratio is correct when the requirements are r(st) = k for all t is an element of T {s}, but for general rooted demands our article implies only ratio O(k(2)) (which, however, is still the currently best-known ratio for the problem). We also obtained various ratios for the node-weighted version of the problem. These results are valid, but the proof needs a correction described here.