International Parallel and Distributed Processing Symposium (IPDPS'03) 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 ISBN: 0-7695-1926-1
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb