Wireless network design via 3-decompositions

We consider some network design problems with applications for wireless networks. The input for these problems is a metric space (X, d) and a finite subset U ⊆ X of terminals. In the Steiner Tree with Minimum Number of Steiner Points (STMSP) problem, the goal is to find a minimum size set S ⊆ X - U of points so that the unit-disc graph of S + U is connected. Let Δ be the smallest integer so that for any finite V ⊆ X for which the unit-disc graph is connected, this graph contains a spanning tree with maximum degree ≤Δ. The best known approximation ratio for STMSP was Δ - 1 [I.I. Mǎndoiu, A.Z. Zelikovsky, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Information Processing Letters 75 (4) (2000) 165-167]. We improve this ratio to ⌊ (Δ + 1) / 2 ⌋ + 1 + ε. In the Minimum Power Spanning Tree (MPST) problem, V = X is finite, and the goal is to find a "range assignment" {p (v) : v ∈ V} on the nodes so that the edge set {u v ∈ E : d (u v) ≤ min {p (u), p (v)}} contains a spanning tree, and ∑_{v ∈ V} p (v) is minimized. We consider a particular case {0, 1}-MPST of MPST when the distances are in {0, 1}; here the goal is to find a minimum size set S ⊆ V of "active" nodes so that the graph (V, E₀ + E₁ (S)) is connected, where E₀ = {u v : d (u v) = 0}, and E₁ (S) is the set the edges in E₁ = {u v : d (u v) = 1} with both endpoints in S. We will show that the (5 / 3 + ε)-approximation scheme for MPST of [E. Althaus, G. Calinescu, I. Mǎndoiu, S. Prasad, N. Tchervenski, A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks 12 (3) (2006) 287-299] achieves a ratio 3/2 for {0, 1}-distances. This answers an open question posed in [E. Lloyd, R. Liu, S. Ravi, Approximating the minimum number of maximum power users in ad hoc networks, Mobile Networks and Applications 11 (2006) 129-142].