In this paper we present a new heuristic called Adaptive Broadcast Consumption (ABC for short) for the Minimum-Energy Broadcast Routing (MEBR) problem. We first investigate the problem trying to understand which are the main properties not taken into account by the classic and well–studied MST and BIP heuristics, then we propose a new algorithm proving that it computes the MEBR with an approximation ratio less than or equal to MST, for which we prove an approximation ratio of at most 12.15 instead of the well–known 12 [10]. Finally we present experimental results supporting our intuitive ideas, comparing ABC with other heuristics presented in the literature and showing its good performance on random instances even compared to the optimum.
Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem
NAVARRA, Alfredo;
2004
Abstract
In this paper we present a new heuristic called Adaptive Broadcast Consumption (ABC for short) for the Minimum-Energy Broadcast Routing (MEBR) problem. We first investigate the problem trying to understand which are the main properties not taken into account by the classic and well–studied MST and BIP heuristics, then we propose a new algorithm proving that it computes the MEBR with an approximation ratio less than or equal to MST, for which we prove an approximation ratio of at most 12.15 instead of the well–known 12 [10]. Finally we present experimental results supporting our intuitive ideas, comparing ABC with other heuristics presented in the literature and showing its good performance on random instances even compared to the optimum.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
