In this paper we discuss the complexity of a dynamic spectrum management problem within a multi-user communication system with K users and N available tones. In this problem a common utility function is optimized. In particular, so called min-rate, harmonic mean and geometric mean utility functions are considered. The complexity of the optimization problems with these utility functions is already discussed in [4] for different cases. However, the complexity for the case N = 2, K arbitrary is an open question. In this paper we show that these cases are also NP- hard by 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.
Article
View On an open question about the complexity of a dynamic spectrum management problem