Computer Science – Networking and Internet Architecture
Scientific paper
2011-12-11
Computer Science
Networking and Internet Architecture
20 pages
Scientific paper
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 sub-optimal but low-complexity algorithms. In this paper, the contributions comprise new insights from revisiting tractability aspects of computing optimum. 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 is restricted to 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 prove optimality guarantee. In addition, we prove that the recognition of this class is polynomial-time solvable.
Ho Chin Keong
Joung Jingon
Sun Sumei
Yuan Di
No associations
LandOfFree
On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-307114