TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem N2 - We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2. T3 - ZIB-Report - 13-54 KW - Primal-Dual Approximation KW - Steiner Connectivity Problem KW - Degree Property KW - Hypergraph Y1 - 2013 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/4243 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-42430 SN - 1438-0064 ER -