Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets

Stefan Funke, Sören LaueSTACS 2007 · OpenReview

Abstract

We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source node s reaches all other nodes within a bounded number k of transmissions and the total amount of assigned energy is minimized. By showing the existence of a coreset of size $O(\left({{1}\over{\epsilon}}\right)^{4k})$ we are able to (1 + ε)-approximate the bounded-hop broadcast problem in time linear in n which is a drastic improvement upon the previously best known algorithm. While actual network deployments often are in a planar setting, the experienced metric for several reasons is typically not exactly of the Euclidean type, but in some sense ’close’. Our algorithm (and others) also work for non-Euclidean metrics provided they exhibit a certain similarity to the Euclidean metric which is known in the literature as bounded doubling dimension. We give a novel characterization of such metrics also pointing out other applications such as space-efficient routing schemes.
BibTeX
@inproceedings{funke2007bounded,
  author = {Stefan Funke and Sören Laue},
  title = {{Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets}},
  booktitle = {STACS},
  year = {2007},
  url = {https://openreview.net/forum?id=YWCDZe0kOeA},
}

Loading related content...

Figure