liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
ASTAR, Singapore .
ASTAR, Singapore .
ASTAR, Singapore .
2013 (English)In: IEEE Transactions on Vehicular Technology, ISSN 0018-9545, E-ISSN 1939-9359, Vol. 62, no 2, 863-873 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE) , 2013. Vol. 62, no 2, 863-873 p.
Keyword [en]
Orthogonal frequency-division multiple access (OFDMA), resource allocation, tractability
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-93408DOI: 10.1109/TVT.2012.2225854ISI: 000318515100033OAI: diva2:624444

Funding Agencies|Swedish Research Council||Linkoping-Lund Excellence Center in Information Technology||Center for Industrial Information Technology of Linkoping University||

Available from: 2013-05-31 Created: 2013-05-31 Last updated: 2013-06-13

Open Access in DiVA

fulltext(281 kB)293 downloads
File information
File name FULLTEXT01.pdfFile size 281 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Yuan, Di
By organisation
Communications and Transport SystemsThe Institute of Technology
In the same journal
IEEE Transactions on Vehicular Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 293 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 59 hits
ReferencesLink to record
Permanent link

Direct link