research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleAn exponential improvement to the MST heuristic for minimum energy broadcasting in ad hoc wireless networks
Bibtex cite IDRACTI-RU1-2007-89
Booktitle 34th International Colloquium on Automata, Languages, and Programming (ICALP 2007)
Year published 2007
Publisher Springer
Note to appear
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.
Caragiannis, Ioannis
Flamini, M
Moscardelli, L
icalp07.pdf (main file)
Publication ID101