License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.60
URN: urn:nbn:de:0030-drops-134042
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13404/
de Berg, Mark ;
Markovic, Aleksandar ;
Umboh, Seeun William
The Online Broadcast Range-Assignment Problem
Abstract
Let P = {p₀,…,p_{n-1}} 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 range-assignment 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 distance-power gradient.
We introduce the online version of the range-assignment 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 1-competitive algorithm does not exist. In particular, for distance-power 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: Nearest-Neighbor (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 distance-power gradient α. We also analyze the following variant of NN in ℝ² for α = 2: 2-Nearest-Neighbor (2-NN) 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 Range-Assignment Problem}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {60:1--60:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13404},
URN = {urn:nbn:de:0030-drops-134042},
doi = {10.4230/LIPIcs.ISAAC.2020.60},
annote = {Keywords: Computational geometry, online algorithms, range assignment, broadcast}
}
|
Keywords: |
|
Computational geometry, online algorithms, range assignment, broadcast |
|
Collection: |
|
31st International Symposium on Algorithms and Computation (ISAAC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
