• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International IFIP-TC6 Networking Conference(NETWORKING 2004); 20040509-20040514; Athens; GR >Adaptive Broadcast Consumption (ABC), a New Heuristic and New Bounds for the Minimum Energy Broadcast Routing Problem
【24h】

Adaptive Broadcast Consumption (ABC), a New Heuristic and New Bounds for the Minimum Energy Broadcast Routing Problem

机译：自适应广播消费（ABC），最小能量广播路由问题的新启发式方法和新方法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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. 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.
机译：在本文中，我们针对最小能量广播路由（MEBR）问题提出了一种新的启发式方法，称为自适应广播消耗（ABC）。我们首先调查问题，试图了解经典和经过精心研究的MST和BIP启发式算法未考虑的主要属性，然后提出一种新算法，证明该算法可计算MEBR的近似比小于或等于MST，我们证明其最大近似值是12.15，而不是众所周知的12。最后，我们提供了支持直觉想法的实验结果，将ABC与文献中提供的其他启发式方法进行了比较，并证明了它在随机实例中的良好性能达到最佳状态。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号