Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
DOI10.1137/23m1545975arXiv2112.05426WikidataQ128178965 ScholiaQ128178965MaRDI QIDQ6202754
Frits C. R. Spieksma, Mark T. de Berg, Arpan Sadhukhan
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
online algorithmscomputational geometrystable approximation schemesbounded recoursebroadcast range assignement
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range assignment for energy efficient broadcasting in linear radio networks
- Online minimization knapsack problem
- A linear-time algorithm for computing the Voronoi diagram of a convex polygon
- Weighted broadcast in linear radio networks
- The minimum range assignment problem on linear radio networks
- Power consumption in packet radio networks
- The minimum broadcast range assignment problem on linear multi-hop wireless networks.
- Online constrained optimization with recourse
- Online Scheduling with Bounded Migration
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
- On the hardness of range assignment problems
- A Robust PTAS for Machine Covering and Packing
- Dynamic Steiner Tree Problem
- On Finding and Updating Spanning Trees and Shortest Paths
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Online Maximum Matching with Recourse
- Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
- Online Bipartite Matching with Amortized O (log 2 n ) Replacements
- Online Steiner Tree with Deletions
- Maintaining Assignments Online: Matching, Scheduling, and Flows
- Automata, Languages and Programming
- The Power of Recourse for Online MST and TSP
- The Online Broadcast Range-Assignment Problem
This page was built for publication: Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem