On the Complexity of Maximizing the Minimum Shannon Capacity by Joint Cell, Channel and Power Allocation in Wireless Communication Networks

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

ovr (ämneskategori)