|
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl. |  |
Type of publication: | Inproceedings |
Entered by: | chita |
Title | An exponential improvement to the MST heuristic for minimum energy broadcasting in ad hoc wireless networks |
Bibtex cite ID | RACTI-RU1-2007-89 |
Booktitle | 34th International Colloquium on Automata, Languages, and Programming (ICALP 2007) |
Year published | 2007 |
Publisher | Springer |
Note | to appear |
URL | http://icalp07.ii.uni.wroc.pl/ |
Abstract | In this paper we present a new approximation algorithm for
the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc
wireless networks that has exponentially better approximation factor
than the well-known Minimum Spanning Tree (MST) heuristic. Namely,
for any instance where a minimum spanning tree of the set of stations
is guaranteed to cost at most ½ times the cost of an optimal solution
for MEBR, we prove that our algorithm achieves an approximation ra-
tio bounded by 2 ln ½ ¡ 2 ln 2 + 2. This result is particularly relevant for
its consequences on Euclidean instances where we signi¯cantly improve
previous results. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments | |
Publication ID | 101 |
|
|