A primaldual approximation algorithm for the survivable network design problem in hypergraph

Abstract. Given a hypergraph with nonnegative costs on hyperedge and a requirement function r: 2V! Z+, where V is the vertex set, we consider the problem of nding a minimum cost hyperedge set F such that for all S V, F contains at least r(S) hyperedges incident to S. In the case that r is weakly supermodular (i.e., r(V) = 0 and r(A) + r(B) maxfr(A \B) + r(A [B); r(AB) + r(B A)g for any A;B V), and the so-called minimum violated sets can be computed in polynomial time, we present a primal-dual approximation algorithm with performance guarantee dmaxH(rmax), where dmax is the maximum degree of the hyperedges with positive cost, rmax is the maximum requirement, andH(i) = i j=