id: 06086350
dt: a
an: 06086350
au: Grandoni, Fabrizio
ti: On min-power Steiner tree.
so: Epstein, Leah (ed.) et al., Algorithms ‒ ESA 2012. 20th annual European
symposium, Ljubljana, Slovenia, September 10‒12, 2012. Proceeding.
Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in
Computer Science 7501, 527-538 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc:
ut:
ci:
li: doi:10.1007/978-3-642-33090-2_46
ab: Summary: In the classical (min-cost) Steiner tree problem, we are given an
edge-weighted undirected graph and a set of terminal nodes. The goal is
to compute a min-cost tree $S$ which spans all terminals. In this paper
we consider the min-power version of the problem (a.k.a. symmetric
multicast), which is better suited for wireless applications. Here, the
goal is to minimize the total power consumption of nodes, where the
power of a node $v$ is the maximum cost of any edge of $S$ incident to
$v$. Intuitively, nodes are antennas (part of which are terminals that
we need to connect) and edge costs define the power to connect their
endpoints via bidirectional links (so as to support protocols with ack
messages). Observe that we do not require that edge costs reflect
Euclidean distances between nodes: this way we can model obstacles,
limited transmitting power, non-omnidirectional antennas etc.
Differently from its min-cost counterpart, min-power Steiner tree is
NP-hard even in the spanning tree case (a.k.a. symmetric connectivity),
i.e. when all nodes are terminals. Since the power of any tree is
within once and twice its cost, computing a $ρ_{st } \leq \ln (4) +
ϵ$ [Byrka et al.’10] approximate min-cost Steiner tree provides a
$2ρ_{st } < 2.78$ approximation for the problem. For min-power
spanning tree the same approach provides a 2 approximation, which was
improved to $5/3 + ϵ$ with a non-trivial approach in [Althaus et
al.’06]. In this paper we present an improved approximation algorithm
for min-power Steiner tree. Our result is based on two main
ingredients. We present the first decomposition theorem for min-power
Steiner tree, in the spirit of analogous structural results for
min-cost Steiner tree and min-power spanning tree. Based on this
theorem, we define a proper LP relaxation, that we exploit within the
iterative randomized rounding framework in [Byrka et al.’10]. A
careful analysis of the decrease of the power of nodes at each
iteration provides a $3\ln 4-\frac{9}{4}+ε<1.91$ approximation factor.
The same approach gives an improved $1.5 + ϵ$ approximation for
min-power spanning tree as well. This matches the approximation factor
in [Nutov and Yaroshevitch’09] for the special case of min-power
spanning tree with edge weights in $\{0,1\}$.
rv: