hide
Free keywords:
-
Abstract:
The state-of-the-art algorithms for geometric Steiner
problems use a two-phase approach based on full Steiner trees
(FSTs). The bottleneck of this approach is the second phase (FST
concatenation phase), in which an optimum Steiner tree is constructed
out of the FSTs generated in the first phase. The hitherto most
successful algorithm for this phase considers the FSTs as edges
of a hypergraph and is based on an LP-relaxation of the minimum spanning
tree in hypergraph (MSTH) problem. In this paper, we compare this
original and some new relaxations of this problem and show their
equivalence, and thereby refute a conjecture in the literature.
Since the second phase can also be formulated as a Steiner
problem in graphs, we clarify the relation of this MSTH-relaxation to
all classical relaxations of the Steiner problem.
Finally, we perform some experiments, both on the quality of the
relaxations and on FST-concatenation methods based on them,
leading to the surprising result that an algorithm of ours
which is designed for general
graphs is superior to the MSTH-approach.
