2026-07-24T00:34:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16175 2024-03-06T10:57:04Z ddc:004 open_access

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem de Berg, Mark Sadhukhan, Arpan Spieksma, Frits Computational geometry online algorithms broadcast range assignment stable approximation schemes 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 range-assignment 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 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 introduce the concept of 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. - 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 1-stable (6+2√5)-approximation algorithm - this algorithm can only handle insertions - a (trivial) 2-stable 2-approximation algorithm, and a 3-stable 1.97-approximation 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 range-assignment 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Arpan Sadhukhan and Frits Spieksma 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.15 urn:nbn:de:0030-drops-161756 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.15 eng https://creativecommons.org/licenses/by/4.0/legalcode