## Samenvatting

Let P be a set of points in ℝ^{d}, where each point p ∊ P has an associated transmission range, denoted p(p). The range assignment p induces a directed communication graph Gp(P) on P, which contains an edge (p, q) iff |pq| ≼ p(p). In the broadcast range-assignment problem, the goal is to assign the ranges such that Gp(P) contains an arborescence rooted at a designated root node and the cost ^{∑}_{p∊P} p(p)^{2} 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 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. (1) For the problem in ℝ^{1}, 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 S^{1} (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 S^{1}, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in ℝ^{1}. (3) For the problem in ℝ^{2}, we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm.

Originele taal-2 | Engels |
---|---|

Pagina's (van-tot) | 790-827 |

Aantal pagina's | 38 |

Tijdschrift | SIAM Journal on Discrete Mathematics |

Volume | 38 |

Nummer van het tijdschrift | 1 |

DOI's | |

Status | Gepubliceerd - 2024 |

### Bibliografische nota

Publisher Copyright:© 2024 Society for Industrial and Applied Mathematics.

### Financiering

Last Received by the editors January 11, 2023; accepted for publication (in revised form) November 13, 2023; published electronically February 9, 2024. A preliminary version of this work appeared in the Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, [LIPIcs Leibniz Int. Proc. Inform. Vol. 227, Schloss Wagstuhl, Wadern, Germany]. https://doi.org/10.1137/23M1545975 Funding: The first, second, and third authors are supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. \dagger Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands ([email protected], [email protected], [email protected]).

Financiers | Financiernummer |
---|---|

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | NETWORKS-024.002.003 |