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

Abstract EN

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 = + ∞ .

Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.