STABLE APPROXIMATION ALGORITHMS FOR THE DYNAMIC BROADCAST RANGE-ASSIGNMENT PROBLEM.

Let P be a set of points in Rd, where each point p ∈ P has an associated transmission range, denoted (p). The range assignment induces a directed communication graph Gp (P) on P, which contains an edge (p, q) iff | pq| (p). In the broadcast range-assignment problem, the goal is to assign the ranges such that (P) contains an arborescence rooted at a designated root node and the costΣ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 \mathrm{A}\mathrm{L}\mathrm{G} that, for any given fixed parameter ε >0, is kε-stable and that maintains a solution with approximation ratio 1 + \ε, where the stability parameter k(\varepsilon) only depends on ε and not on the size of P. We study such trade-offs in three settings. (1) For the problem in R¹, 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 S1 (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 S1, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in R¹. (3) For the problem in R2, we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results γ generalize to the setting where, for any given constant α > 1, the range-assignment cost is pΣ (p)∈α. [ABSTRACT FROM AUTHOR]