de Berg, Mark ;
Markovic, Aleksandar ;
Umboh, Seeun William
The Online Broadcast RangeAssignment Problem
Abstract
Let P = {p₀,…,p_{n1}} be a set of points in ℝ^d, modeling devices in a wireless network. A range assignment assigns a range r(p_i) to each point p_i ∈ P, thus inducing a directed communication graph 𝒢_r in which there is a directed edge (p_i,p_j) iff dist(p_i, p_j) ⩽ r(p_i), where dist(p_i,p_j) denotes the distance between p_i and p_j. The rangeassignment problem is to assign the transmission ranges such that 𝒢_r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by ∑_{p_i ∈ P} r(p_i)^α, for some constant α > 1 called the distancepower gradient.
We introduce the online version of the rangeassignment problem, where the points p_j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away  in our case this means that the transmission ranges will never decrease. The property we want to maintain is that 𝒢_r has a broadcast tree rooted at the first point p₀. Our results include the following.
 We prove that already in ℝ¹, a 1competitive algorithm does not exist. In particular, for distancepower gradient α = 2 any online algorithm has competitive ratio at least 1.57.
 For points in ℝ¹ and ℝ², we analyze two natural strategies for updating the range assignment upon the arrival of a new point p_j. The strategies do not change the assignment if p_j is already within range of an existing point, otherwise they increase the range of a single point, as follows: NearestNeighbor (NN) increases the range of NN(p_j), the nearest neighbor of p_j, to dist(p_j, NN(p_j)), and Cheapest Increase (CI) increases the range of the point p_i for which the resulting cost increase to be able to reach the new point p_j is minimal. We give lower and upper bounds on the competitive ratio of these strategies as a function of the distancepower gradient α. We also analyze the following variant of NN in ℝ² for α = 2: 2NearestNeighbor (2NN) increases the range of NN(p_j) to 2⋅ dist(p_j,NN(p_j)),
 We generalize the problem to points in arbitrary metric spaces, where we present an O(log n)competitive algorithm.
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs:2020:13404,
author = {Mark de Berg and Aleksandar Markovic and Seeun William Umboh},
title = {{The Online Broadcast RangeAssignment Problem}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {60:160:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13404},
URN = {urn:nbn:de:0030drops134042},
doi = {10.4230/LIPIcs.ISAAC.2020.60},
annote = {Keywords: Computational geometry, online algorithms, range assignment, broadcast}
}
04.12.2020
Keywords: 

Computational geometry, online algorithms, range assignment, broadcast 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 