loading...
On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks
Nice, France April 22-April 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213407International Parallel and Distribute ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Andrea E.F. Clementi, Gurvan Huiban, Paolo Penna, "On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks," Parallel and Distributed Processing Symposium, International, pp. 222a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/IPDPS.2003.1213407,
author = {Andrea E.F. Clementi and Gurvan Huiban and Paolo Penna},
title = {On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks},
journal ={Parallel and Distributed Processing Symposium, International},
volume = {0},
year = {2003},
issn = {1530-2075},
pages = {222a},
doi = {http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213407},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Processing Symposium, International
TI - On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks
SN - 1530-2075
SP
EP
A1 - Andrea E.F. Clementi,
A1 - Gurvan Huiban,
A1 - Paolo Penna,
PY - 2003
KW - Power controlled ad-hoc radio networks
KW - Approximation algorithms
KW - Minimum spanning tree
VL - 0
JA - Parallel and Distributed Processing Symposium, International
ER -
 
Andrea E.F. Clementi, Università di Roma "Tor Vergata"
Gurvan Huiban, Università di Roma "Tor Vergata"
Paolo Penna, Università di Salerno

We present a technique to evaluate the approximation ratio on random instances of the Minimum Energy Broadcast Problem in Ad-Hoc Radio Networks which is known to be NP-hard and approximable within 12. Our technique relies on polynomial-time computable lower bound on the optimal cost of any instance.

The main result of this paper is that the approximation ratio has never achieved a value greater than 6.4. Furthermore, the worst values of this ratio are achieved for small network sizes. We also provide a clear geometrical motivation of such good approximation results.

Index Terms:
Power controlled ad-hoc radio networks, Approximation algorithms, Minimum spanning tree
Citation:
Andrea E.F. Clementi, Gurvan Huiban, Paolo Penna, "On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks," ipdps, pp.222a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.