Date Added: Jan 2012
The authors give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, they give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sub-linear power assignment. For the case of uniform power, they extend this to the case of variable QoS requirements and link-dependent noise terms. Second, they approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, they obtain constant-factor approximation of weighted capacity under linear power assignment.