A primal–dual approximation algorithm for the survivable network design problem in hypergraphs Original Research Article

Given a hypergraph with nonnegative costs on hyperedges, and a weakly supermodular function r : 2V→Z+, where V is the vertex set, we consider the problem of finding a minimum cost subset of hyperedges such that for every set S⊆V, there are at least r(S) hyperedges that have at least one but no all endpoints in S. This problem captures a hypergraph generalization of the survivable network design problem (SNDP), and also the element connectivity problem (ECP). We present a primal–dual algorithm with a performance guarantee of dmax+H(rmax), where dmax+ is the maximum degree of hyperedges of positive costs, rmax=maxS r(S), and H(k)=1+12+⋯+1k. In particular, our result contains a 2H(rmax)-approximation algorithm for ECP, which gives an independent and complete proof for the result first obtained by Jain et al. (Proceedings of the SODA, 1999, p. 484–489).