Approximation Algorithms for Maximum Weight Independent Set of Links Under the SINR Model
Lixin Wang and Xiaohua Xu
We study the following optimization problem in a plane multihop wireless network under the physical interference model. Given a multihop wireless network and a positive link weight (or demand) function, select a set of independent links whose total weight is maximized. This problem is known to be NP-hard. The best known approximation algorithms for this problem achieved logarithmic-factor approximation bounds with either the uniform power assignment or the power control setting. In this paper, we present two approximation algorithms for the problem with pre-specified power assignments. The first algorithm uses the oblivious power assignment and achieves constant approximation bound under certain mild assumptions. The second algorithm achieves constant approximation bound when the link weight-to-length ratio is bounded. Moreover, our constant approximation bounds are valid regardless of the value of the noise power.
Keywords: Physical interference model, approximation algorithm, maximum independent set, link scheduling