Wireless Capacity With Arbitrary Gain Matrix.

link: http://arxiv.org/abs/1108.1055
Abstract

Given a set of wireless links, a fundamental problem is to find the largest
subset that can transmit simultaneously, within the SINR model of interference.
Significant progress on this problem has been made in recent years. In this
note, we study the problem in the setting where we are given a fixed set of
arbitrary powers each sender must use, and an arbitrary gain matrix defining
how signals fade. This variation of the problem appears immune to most
algorithmic approaches studied in the literature. Indeed it is very hard to
approximate since it generalizes the max independent set problem. Here, we
propose a simple semi-definite programming approach to the problem that yields
constant factor approximation, if the optimal solution is strictly larger than
half of the input size.