A new distributed approximation algorithm for the maximum weight independent set problem (Q1793873): Difference between revisions
From MaRDI portal
Latest revision as of 21:45, 16 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new distributed approximation algorithm for the maximum weight independent set problem |
scientific article |
Statements
A new distributed approximation algorithm for the maximum weight independent set problem (English)
0 references
12 October 2018
0 references
Summary: 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 \(H\) 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 = + \infty\). Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.
0 references
0 references
0 references