Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets
Lists
Only you see this
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...