Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:liu:diva-93408DOI: 10.1109/TVT.2012.2225854ISI: 000318515100033OAI: oai:DiVA.org:liu-93408DiVA: diva2:624444
Note

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: 2017-12-06

Open Access in DiVA

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

Other links

Publisher's full text

Authority records BETA

Yuan, Di

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: 365 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 108 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf