Given a hypergraph with nonnegative costs on hyperedge and a requirement function r : 2{sup}V→Z{sup}+, where V is the vertex set, we consider the problem of finding a minimum cost hyperedge set F such that for all S is contained in 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) ≤ max {r(A ∩ B) + r(A ∪ B), r(A－B) + r(B－A)} for any A,B is contained in V), and the so-called minimum violated sets can be computed in polynomial time, we present a primal-dual approximation algorithm with performance guarantee d{sub}(max) H (r{sub}(max))), where d{sub}(max) is the maximum degree of the hyperedges with positive cost, r{sub}(max) is the maximum requirement, and H(i)=∑{sub}(j=1){sup}i (1/j) is the harmonic function. In particular, our algorithm can be applied to the survivable network design problem in which the requirement is that there should be at least r{sub}(st) hyperedge-disjoint paths between each pair of distinct vertices s and t, for which r{sub}(st) is prescribed.
展开▼
