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

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)

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 ² 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