Optimization Online


On an open question about the complexity of a dynamic spectrum management problem

M. Locatelli(marco.locatelli***at***unipr.it)
Z.-Q. Luo(luozq***at***ece.umn.edu)

Abstract: 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.

Keywords: Dynamic Spectrum Management, Complexity, Partitioning Problem, Independent Set

Category 1: Global Optimization (Theory )

Category 2: Applications -- OR and Management Sciences (Telecommunications )


Download: [PDF]

Entry Submitted: 12/10/2014
Entry Accepted: 12/10/2014
Entry Last Modified: 12/10/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society