Gaussian downlink user selection subject to access limit, power budget, and rate demands

Consider a Gaussian downlink between an access point with power budget , and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit is imposed on the number of superimposed users. For each subset of users, its (total) power demand is a strictly increasing and nonseparable function of the effective noises and rate demands of users in . A subset of users is feasible if and . The goal is to select a feasible subset of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a -approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency.