On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems

• Published in: IEEE transactions on vehicular technology 2013-02, Vol.62 (2), p.863-873
• Main Authors: Yuan, Di, Joung, Jingon, Ho, Chin Keong, Sun, Sumei
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Allocations; Applied sciences; Channel allocation; Channels; Complexity theory; Exact sciences and technology; Information, signal and communications theory; Mathematical analysis; Mathematical models; Multiple access; Multiplexing; Optimization; Orthogonal frequency-division multiple access (OFDMA); Polynomials; Resource allocation; Resource management; Signal and communications theory; Signal to noise ratio; Studies; Systems, networks and services of telecommunications; TECHNOLOGY; TEKNIKVETENSKAP; Telecommunications; Telecommunications and information theory; tractability; Transmission and modulation (techniques and equipments)
• ISSN: 0018-9545; 1939-9359; 1939-9359
• DOI: 10.1109/TVT.2012.2225854

Joint channel and rate allocation with power minimization in orthogonal frequency-division multiple access (OFDMA) has attracted extensive attention. Most of the research has dealt with the development of suboptimal but low-complexity algorithms. In this paper, the contributions comprise new insights from revisiting tractability aspects of computing the optimum solution. Previous complexity analyses have been limited by assumptions of fixed power on each subcarrier or power-rate functions that locally grow arbitrarily fast. The analysis under the former assumption does not generalize to problem tractability with variable power, whereas the latter assumption prohibits the result from being applicable to well-behaved power-rate functions. As the first contribution, we overcome the previous limitations by rigorously proving the problem's NP-hardness for the representative logarithmic rate function. Next, we extend the proof to reach a much stronger result, namely, that the problem remains NP-hard, even if the channels allocated to each user are restricted to be a consecutive block with given size. We also prove that, under these restrictions, there is a special case with polynomial-time tractability. Then, we treat the problem class where the channels can be partitioned into an arbitrarily large but constant number of groups, each having uniform gain for every individual user. For this problem class, we present a polynomial-time algorithm and provide its optimality guarantee. In addition, we prove that the recognition of this class is polynomial-time solvable.