A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem. (6th September 2016)

• Record Type: Journal Article
• Authors: Du, Peng; Zhang, Yuan
• Other Names: Simon Dan Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2016(2016)
• Publication Date: 2016-09-06
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2016/9790629
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : 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 parameterH 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 withH = + ∞ . Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.