On Min-Power Steiner Tree

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

 ≤ 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}+\varepsilon <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}.