On the complexity of maximizing the minimum Shannon capacity in wireless networks by joint channel assignment and power allocation
2010 (English)In: 2010 18th International Workshop on Quality of Service (IWQoS), IEEE , 2010, 5542766- p.Conference paper (Refereed)
We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequency-division multiple access (OFDMA). For a given snap-shot in time, two joint channel assignment and power allocation optimization problems are presented, one in downlink and one in uplink. The objective is to maximize the minimum total Shannon capacity of any mobile user in the system, subject to system constraints. The corresponding decision problems are proved to be NP-hard. We also show that for any constant ρ > 0, a sufficiently large number of channels ensure that the optimization problems are not ρ-approximable, unless P is equal to NP.
Place, publisher, year, edition, pages
IEEE , 2010. 5542766- p.
, IEEE International Workshop on Quality of Service, IWQoS, ISSN 1548-615X
Channel Assignment, Decision problems, Mobile users, NP-hard, Optimization problems, Orthogonal frequencies, Orthogonal frequency division multiple access, Power allocations, Shannon capacity, System constraints, Wireless telecommunications
IdentifiersURN: urn:nbn:se:kth:diva-149588DOI: 10.1109/IWQoS.2010.5542766ScopusID: 2-s2.0-77956634718ISBN: 978-142445988-9OAI: oai:DiVA.org:kth-149588DiVA: diva2:740673
2010 IEEE 18th International Workshop on Quality of Service, IWQoS 2010, 16 June 2010 through 18 June 2010, Beijing, China
QC 201408262014-08-262014-08-252014-08-26Bibliographically approved