文章基本信息
- 标题：The Online Broadcast Range-Assignment Problem
- 本地全文：下载
- 作者：Mark de Berg ; Aleksandar Markovic ; Seeun William Umboh 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：181
- 页码：1-15
- DOI：10.4230/LIPIcs.ISAAC.2020.60
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：Computational geometry; online algorithms; range assignment; broadcast
