Abstract
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 language | English (US) |
|---|---|
| Article number | 8006254 |
| Pages (from-to) | 6622-6627 |
| Number of pages | 6 |
| Journal | IEEE Transactions on Information Theory |
| Volume | 63 |
| Issue number | 10 |
| DOIs | |
| State | Published - 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.
Keywords
- Dynamic spectrum management
- complexity
- independent set
- partitioning problem