• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Problems in Engineering >A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem
【24h】

A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem

机译：最大权重独立集问题的一种新的分布式近似算法

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

摘要

Maximum weight independent set (MWIS) is a combinatorial optimization problem that naturally arises in many applications especially wireless networking. This paper studies distributed approximation algorithms for finding MWIS in a general graph. In the proposed algorithm, each node keeps exchanging messages with neighbors in which each message contains partial solutions of the MWIS optimization program. A parameter.. is introduced to achieve different tradeoff between approximation accuracy and space complexity. Theoretical analysis shows that the proposed algorithm is guaranteed to converge to an approximate solution after finite iterations; specifically, the proposed algorithm is guaranteed to converge to the optimal solution with H = +infinity. Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.
机译：最大权重独立集（MWIS）是一个组合优化问题，在许多应用程序中，特别是在无线网络中自然会出现。本文研究了在一般图中寻找MWIS的分布式近似算法。在提出的算法中，每个节点与邻居保持交换消息，其中每个消息包含MWIS优化程序的部分解决方案。引入参数以实现近似精度和空间复杂度之间的不同折衷。理论分析表明，所提算法在有限迭代后可以收敛到近似解。特别地，所提出的算法可以保证收敛到H = +无穷大的最优解。仿真结果证实了所提出的分布式算法在权重总和，消息大小和收敛性能方面的有效性。

著录项

  • 来源
    《Mathematical Problems in Engineering》 |2016年第9期|9790629.1-9790629.10|共10页
  • 作者

    Du Peng; Zhang Yuan;

  • 作者单位

    Nanjing Univ Posts & Telecommun, Coll Automat, Nanjing 210023, Jiangsu, Peoples R China;

    Southeast Univ, Natl Mobile Commun Res Lab, Nanjing, Jiangsu, Peoples R China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号