About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
Abstract
There is an error in our paper "An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems" (Algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirected graph and values rij for each pair of vertices i and j, find a minimum-cost set of edges such that there are rij vertex-disjoint paths between vertices i and j. We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal-dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case rij = k for all i, j, we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2H(k) times optimal, where H(n) = 1 + 1/2 + ... + 1/n. This result is erroneous. We describe an example where our primal-dual augmentation subroutine, when augmenting a k-vertex connected graph to a (k + l)-vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case rij ∈ {0, 1,2} for all i, j, we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k-vertex connected case does hold, and that the algorithm performs as claimed.