## Abstract

Let P= { p, … , p_{n}_{-}_{1}} be a set of points in R^{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 G_{r} in which there is a directed edge (p_{i}, p_{j}) iff dist(pi,pj)⩽r(pi) , where dist(pi,pj) denotes the distance between p_{i} and p_{j} . The range-assignment problem is to assign the transmission ranges such that G_{r} has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by ∑pi∈Pr(pi)α , 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 G_{r} has a broadcast tree rooted at the first point p . Our results include the following. We prove that already in R^{1} , 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 R^{1} and R^{2} , 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(pj) , the nearest neighbor of p_{j} , to dist(pj,nn(pj)) , 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 R^{2} for α= 2 : 2-Nearest-Neighbor (2-nn) increases the range of nn(pj) to 2·dist(pj,nn(pj)) ,We generalize the problem to points in arbitrary metric spaces, where we present an O(log n) -competitive algorithm.

Original language | English |
---|---|

Pages (from-to) | 3928-3956 |

Number of pages | 29 |

Journal | Algorithmica |

Volume | 85 |

Issue number | 12 |

DOIs | |

Publication status | Published - Dec 2023 |

### Funding

Open Access funding enabled and organized by CAUL and its Member Institutions This work was supported by the Dutch Research Council (NWO) under projects no. 024.002.003 and no. 639.022.211.

Funders | Funder number |
---|---|

CAUL | |

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 639.022.211, 024.002.003 |

## Keywords

- Broadcast
- Computational geometry
- Online algorithms
- Range assignment