Abstract
Let P be a set of points in ℝ^d (or some other metric space), where each point p ∈ P has an associated transmission range, denoted ρ(p). The range assignment ρ induces a directed communication graph G_{ρ}(P) on P, which contains an edge (p,q) iff pq ⩽ ρ(p). In the broadcast rangeassignment problem, the goal is to assign the ranges such that G_{ρ}(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 tradeoffs 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 introduce the concept of kstable 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 tradeoffs in three settings.
 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 algorithms with very small stability parameters: a 1stable (6+2√5)approximation algorithm  this algorithm can only handle insertions  a (trivial) 2stable 2approximation algorithm, and a 3stable 1.97approximation algorithm.
 For the problem in ?¹ (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 ?¹, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in ℝ¹.
 For the problem in ℝ², we also prove that no SAS exists, and we present a O(1)stable O(1)approximation algorithm. Most results generalize to when the rangeassignment cost is ∑_{p ∈ P} ρ(p)^{α}, for some constant α > 1. All omitted theorems and proofs are available in the full version of the paper [Mark de Berg et al., 2021].
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs.SWAT.2022.15,
author = {de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits},
title = {{Stable Approximation Algorithms for the Dynamic Broadcast RangeAssignment Problem}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {15:115:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16175},
URN = {urn:nbn:de:0030drops161756},
doi = {10.4230/LIPIcs.SWAT.2022.15},
annote = {Keywords: Computational geometry, online algorithms, broadcast range assignment, stable approximation schemes}
}
Keywords: 

Computational geometry, online algorithms, broadcast range assignment, stable approximation schemes 
Collection: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) 
Issue Date: 

2022 
Date of publication: 

22.06.2022 