A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem
Please always quote using this URN: urn:nbn:de:0297-zib-42430
- 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.
Download full text files
Additional Services
| Author: | Ralf BorndörferORCiD, Marika Karbstein |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Degree Property; Hypergraph; Primal-Dual Approximation; Steiner Connectivity Problem |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C40 Connectivity |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics | |
| Date of first Publication: | 2013/11/09 |
| Series (Serial Number): | ZIB-Report (13-54) |
| ISSN: | 1438-0064 |
