On the approximation ratio of the MST based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks

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.