In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum-Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d ≥ 2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, as a limit for α going to infinity, the ratio tends to the lower bound of [3, 15] given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.6-approximation ratio for the 2-dimensional case, thus signifcantly decreasing the previously known 12 upper bound [15] (actually corrected to 12.15 in [10]). Starting from the above results, such an approximation holds for any α ≥ 2. Finally, we extend our analysis to any number of dimensions d ≥ 2 and any α ≥ d, obtaining a general approximation ratio of 3^d-1, independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. Note that for α ‹ d the ratios cannot be bounded by any function of α and d [3].
Improved approximation results for the Minimum Energy Broadcasting Problem
NAVARRA, Alfredo;
2004
Abstract
In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum-Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d ≥ 2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, as a limit for α going to infinity, the ratio tends to the lower bound of [3, 15] given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.6-approximation ratio for the 2-dimensional case, thus signifcantly decreasing the previously known 12 upper bound [15] (actually corrected to 12.15 in [10]). Starting from the above results, such an approximation holds for any α ≥ 2. Finally, we extend our analysis to any number of dimensions d ≥ 2 and any α ≥ d, obtaining a general approximation ratio of 3^d-1, independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. Note that for α ‹ d the ratios cannot be bounded by any function of α and d [3].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
