  


On an open question about the complexity of a dynamic spectrum management problem
M. Locatelli(marco.locatelliunipr.it) Abstract: In this paper we discuss the complexity of a dynamic spectrum management problem within a multiuser communication system with K users and N available tones. In this problem a common utility function is optimized. In particular, so called minrate, 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 minrate 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 ) Citation: Download: [PDF] Entry Submitted: 12/10/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  