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.
On the Complexity of Optimal Power Allocation in a Multi-Tone Multiuser Communication System / Locatelli, Marco; Luo, Zhi-Quan. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - 63:10(2017), pp. 6622-6627. [10.1109/TIT.2017.2737536]
On the Complexity of Optimal Power Allocation in a Multi-Tone Multiuser Communication System
Locatelli, Marco;
2017-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.