We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., Orthogonal Frequency-Division Multiple Access (OFDMA). For a given snap-shot in time, the joint cell, channel and power allocation optimization problem is presented, both in downlink and in uplink. The objective is to maximize the minimum total Shannon capacity of any mobile user in the system, subject to system constraints. The corresponding decision problems are proved to be NP-hard. We also show that for any constant ρ > 0, a sufficiently large number of channels ensure that the optimization problems are not ρ-approximable, unless P is equal to NP. Furthermore, we show that the inapproximability property remains when solely considering the power allocation problem, i.e., given a feasible cell and channel allocation. This power allocation optimization problem is not convex in general, but in the simplified setting where each transmitter is allowed to use only one single channel, there exists known approaches to attain the global optimum. In this setting, we prove that any solution that fulfills the KKT conditions is a global optimum.
Condensed version published in
IEEE International Workshop on Quality of Service