Name
Title | ||
|---|---|---|
A primal-dual approximation algorithm for the survivable network design problem in hypergraphs |
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(A B) + 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, and H(i) = i j=1 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 rst hyperedge-disjoint paths between each pair of distinct vertices s and t, for which rst is prescribed. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0166-218X(02)00201-9 | Symposium on Theoretical Aspects of Computer Science |
Keywords | DocType | Volume |
maximum degree,hyperedges incident,hypergraph generalization,nonnegative cost,primal-dual approximation algorithm,minimum cost subset,minimum cost hyperedge set,maximum requirement,requirement function,approximation algorithm,positive cost,harmonic function,element connectivity problem,maxs r,complete proof,primal-dual algorithm,vertex set,rst hyperedge-disjoint path,survivable network design problem,polynomial time | Conference | 126 |
Issue | ISSN | ISBN |
2-3 | Discrete Applied Mathematics | 3-540-41695-1 |
Citations | PageRank | References |
4 | 0.81 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liang Zhao | 1 | 131 | 24.39 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |