We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequencydivision multiple access (OFDMA). For a snap-shot in time, a joint channel assignment and power allocation optimization problem is presented, both in downlink and in uplink, where the objective is to maximize the minimum total Shannon capacity of any mobile user in the system. The corresponding decision problem is proved to be NP-hard. Another proof gives that for any constant $rho$ > 0, a sufficiently large number of channels ensures that the optimization problem is not $rho$-approximable, unless P is equal to NP. If assuming that the channel allocation is known, the remaining power allocation optimization problem also has this inapproximability property. This power allocation optimization problem formulation is not convex in general. However, if each transmitter only is allowed to use one single channel, then it is shown that every KKT point is a global optimum.
Citation
Report number: TRITA 8, Address: Department of Mathematics, Royal Institute of Technology, SE-100 44 Stockholm, Sweden, month/year: 12/2009.