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

摘要

Consider a multi-tone multi-user communication system with interfering users and 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 ( ) 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 . 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.