Optimal Joint Subcarrier and Power Allocation in Power-Domain NOMA is Strongly NP-Hard: Complexity Analysis

Speaker : Lou Salaun
Nokia Bell Labs
Date: 15/11/2017
Time: 2:00 pm - 3:00 pm
Location: LINCS Seminars room


Non-orthogonal multiple access (NOMA) is a promising radio access technology for 5G. It allows several users to transmit on the same frequency and time resource by performing power-domain multiplexing. At the receiver side, successive interference cancellation (SIC) is applied to mitigate interference among the multiplexed signals. In this way, NOMA can outperform orthogonal multiple access schemes used in conventional cellular networks in terms of spectral efficiency and allows more simultaneous users. We investigate the computational complexity of joint subcarrier and power allocation problems in multi-carrier NOMA systems. In this talk, we will show that these problems are strongly NP-hard for a large class of objective functions, namely the weighted generalized means of the individual data rates. This class covers the popular weighted sum-rate, proportional fairness, harmonic mean and max-min fairness utilities. This result implies that the optimal power and subcarrier allocation cannot be computed in polynomial time in the general case, unless P = NP. Nevertheless, we present some heuristics and show their performance through numerical results.