We present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that achieves an exponentially better approximation factor compared to 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 ρ ≥ 2 times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2lnρ-2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results. In this respect, our experimental analysis confirms the better performance of the algorithm also in practice.

An exponential improvement on the MST heuristic for the Minimum Energy Broadcasting problem

FLAMMINI, MICHELE;
2013-01-01

Abstract

We present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that achieves an exponentially better approximation factor compared to 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 ρ ≥ 2 times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2lnρ-2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results. In this respect, our experimental analysis confirms the better performance of the algorithm also in practice.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/4758
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact