Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Let P be a set of points in ℝ^d, where each point p ∊ P has an associated transmission range, denoted p(p). The range assignment p induces a directed communication graph Gp(P) on P, which contains an edge (p, q) iff |pq| ≼ p(p). In the broadcast range-assignment problem, the goal is to assign the ranges such that Gp(P) contains an arborescence rooted at a designated root node and the cost ^∑_p∊P p(p)² of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution-the number of ranges that are modified when a point is inserted into or deleted from P-and its approximation ratio. To this end we study k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm ALG that, for any given fixed parameter ε > 0, is k(ε)stable and that maintains a solution with approximation ratio 1 + ε, where the stability parameter k(ε) only depends on ε and not on the size of P. We study such trade-offs in three settings. (1) For the problem in ℝ¹, we present a SAS with k(ε) = O(1/ε). Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have k(ε) = Ω(1/ε). We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in S¹ (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in S¹, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in ℝ¹. (3) For the problem in ℝ², we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm.