Optimization Online


On the complexity of maximizing the minimum Shannon capacity in wireless networks by joint channel assignment and power allocation

Mikael Fallgren(werty***at***kth.se)

Abstract: We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequencydivision multiple access (OFDMA). For a snap-shot in time, a joint channel assignment and power allocation optimization problem is presented, both in downlink and in uplink, where the objective is to maximize the minimum total Shannon capacity of any mobile user in the system. The corresponding decision problem is proved to be NP-hard. Another proof gives that for any constant $rho$ > 0, a sufficiently large number of channels ensures that the optimization problem is not $rho$-approximable, unless P is equal to NP. If assuming that the channel allocation is known, the remaining power allocation optimization problem also has this inapproximability property. This power allocation optimization problem formulation is not convex in general. However, if each transmitter only is allowed to use one single channel, then it is shown that every KKT point is a global optimum.

Keywords: wireless telecommunication, OFDMA

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

Citation: Report number: TRITA 8, Address: Department of Mathematics, Royal Institute of Technology, SE-100 44 Stockholm, Sweden, month/year: 12/2009.

Download: [PDF]

Entry Submitted: 01/18/2010
Entry Accepted: 01/18/2010
Entry Last Modified: 01/18/2010

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 Programming Society