非表示:
キーワード:
-
要旨:
The group Steiner tree problem is a generalization of the
Steiner tree problem where we are given several subsets (groups) of
vertices in
a weighted graph,
and the goal is to find a minimum-weight connected subgraph containing
at least one vertex from each group. The problem was introduced by
Reich and Widmayer and finds applications in VLSI design.
The group Steiner tree problem generalizes the set covering
problem, and is therefore at least as hard.
We give a randomized $O(\log^3 n \log k)$-approximation
algorithm for the group Steiner tree problem on an $n$-node graph, where
$k$ is the number of groups.The best previous performance guarantee was
$(1+\frac{\ln k}{2})\sqrt{k}$ (Bateman, Helvig, Robins and Zelikovsky).
Noting that the group Steiner problem also models the
network design problems with location-theoretic constraints studied by
Marathe, Ravi and Sundaram, our results also improve their bicriteria
approximation results. Similarly, we improve previous results by
Slav{\'\i}k on a tour version, called the errand scheduling problem.
We use the result of Bartal on probabilistic approximation of finite
metric spaces by tree metrics
to reduce the problem to one in a tree metric. To find a solution on a
tree,
we use a generalization of randomized rounding. Our approximation
guarantees
improve to $O(\log^2 n \log k)$ in the case of graphs that exclude
small minors by using a better alternative to Bartal's result on
probabilistic approximations of metrics induced by such graphs
(Konjevod, Ravi and Salman) -- this improvement is valid for the group
Steiner problem on planar graphs as well as on a set of points in the
2D-Euclidean case.
