On the Complexity of Optimal Power Allocation in a Multi-Tone Multiuser Communication System

Marco Locatelli, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review


Consider a multi-tone multi-user communication system with K interfering users and N available tones. An effective approach to mitigate interference is through power control at transmitters. In this paper, we consider optimal power allocation to maximize a system utility function, and show that for the two tone cases (N=2) with min-rate, harmonic mean, and geometric mean utility functions, the corresponding optimal power allocation problem is NP-hard. This result fills an important gap in the existing literature, which settled the complexity status of different cases involving various utility functions and values of N. Our proof is through a reduction from the partitioning problem for the min-rate utility function, and from the independent set problem for the harmonic mean and geometric mean utility functions.

Original languageEnglish (US)
Article number8006254
Pages (from-to)6622-6627
Number of pages6
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 2017

Bibliographical note

Funding Information:
Manuscript received September 11, 2015; revised January 26, 2017; accepted August 3, 2017. Date of publication August 9, 2017; date of current version September 13, 2017. This work was supported in part by NSF under Grant CCF-1526434, in part by the Natural Science Foundation of China under Grant 61571384, and in part by the Leading Talents of Guang Dong Province Program under Grant 00201510.

Publisher Copyright:
© 1963-2012 IEEE.


  • Dynamic spectrum management
  • complexity
  • independent set
  • partitioning problem


Dive into the research topics of 'On the Complexity of Optimal Power Allocation in a Multi-Tone Multiuser Communication System'. Together they form a unique fingerprint.

Cite this