Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

DOI10.1137/23M1545975MaRDI QIDQ6202754zbMATH OpenWikidataFDO

Authors Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma

Publication date 27 February 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.05426

zbMATH Keywords

online algorithmscomputational geometrystable approximation schemesbounded recoursebroadcast range assignement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete geometry (52C99)

Abstract: Let $P$ be a set of points in $mathbb{R}^d$, where each point $pinP$ has an associated transmission range $ho(p)$. The range assignment $ho$ induces a directed communication graph $mathcal{G}_{ho}(P)$ on $P$, which contains an edge $(p,q)$ iff $|pq|leqho(p)$. In the broadcast range-assignment problem, the goal is to assign the ranges such that $mathcal{G}_{ho}(P)$ contains an arborescence rooted at a designated node and whose cost $su{m}_{pinP}ho(p{)}^2$ is minimized. 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. We introduce $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 (SAS). A SAS is an update algorithm that, for any given fixed parameter $varepsilon>0$, is $k(epsilon)$-stable and maintains a solution with approximation ratio $1+varepsilon$, where the stability parameter $k(varepsilon)$ only depends on $varepsilon$ and not on the size of $P$. We study such trade-offs in three settings. - In $mathbb{R}^1$, we present a SAS with $k(varepsilon)=O(1/varepsilon)$, which we show is tight in the worst case. We also present a 1-stable $(6+2sqrt5)$-approximation algorithm, a $2$-stable 2-approximation algorithm, and a $3$-stable $1.97$-approximation algorithm. - In $mathbb{S}^1$ (where the underlying space is a circle) we prove that no SAS exists, even though an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in $mathbb{R}^1$. - In $mathbb{R}^2$, we also prove that no SAS exists, and we present a $O(1)$-stable $O(1)$-approximation algorithm.

Cites work

• scientific article; zbMATH DE number 1979511 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• A Robust PTAS for Machine Covering and Packing
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Automata, Languages and Programming
• Computational geometry. Algorithms and applications.
• Dynamic Steiner Tree Problem
• Fully Dynamic Matching: Beating 2-Approximation in Δ^ϵ Update Time
• Introduction to algorithms.
• Maintaining assignments online: matching, scheduling, and flows
• On Finding and Updating Spanning Trees and Shortest Paths
• On the hardness of range assignment problems
• Online Steiner tree with deletions
• Online bipartite matching with amortized O(^2 n) replacements
• Online constrained optimization with recourse
• Online maximum matching with recourse
• Online minimization knapsack problem
• Online scheduling with bounded migration
• Power consumption in packet radio networks
• Range assignment for energy efficient broadcasting in linear radio networks
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The Online Broadcast Range-Assignment Problem
• The minimum broadcast range assignment problem on linear multi-hop wireless networks.
• The minimum range assignment problem on linear radio networks
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP
• Weighted broadcast in linear radio networks

Cited in

(2)

• Stable approximation algorithms for dominating set and independent set
• Online range assignment problems

This page was built for publication: Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202754)