Refine
Year of publication
- 2013 (6) (remove)
Document Type
- ZIB-Report (3)
- Article (1)
- Book chapter (1)
- In Proceedings (1)
Language
- English (6) (remove)
Is part of the Bibliography
- no (6)
Keywords
- Degree Property (1)
- Hypergraph (1)
- Primal-Dual Approximation (1)
- Steiner Connectivity Problem (1)
- Steiner connectivity (1)
- Steiner tree (1)
- Steiner tree packing (1)
- combinatorial optimization (1)
- line planning (1)
- polyhedral combinatorics (1)
Institute
Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.
We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.
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.