License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.15
URN: urn:nbn:de:0030-drops-161756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16175/
de Berg, Mark ;
Sadhukhan, Arpan ;
Spieksma, Frits
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
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},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16175},
URN = {urn:nbn:de:0030-drops-161756},
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 |
