When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.15
URN: urn:nbn:de:0030-drops-161756
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16175/
 Go to the corresponding LIPIcs Volume Portal

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

 pdf-format:

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 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].

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 Range-Assignment Problem}},
booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages =	{15:1--15:21},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-236-5},
ISSN =	{1868-8969},
year =	{2022},
volume =	{227},
editor =	{Czumaj, Artur and Xin, Qin},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},