Orthogonal Frequency Division Multiple Access

Orthogonal Frequency Division Multiplexing (OFDM) has become the de facto standard for fourth generation wireless networks[5]. In such a network, the frequency band is divided into numerous orthogonal sub-carriers. In each time-slot, disjoint sets of sub-carriers can be assigned to users based on some target objective. The users in turn transmit data by spreading the information across the as-signed sub-carriers. The main contribution of this work is a formal analysis of the complexity of this class of re-source allocation problems for various objectives and sce-narios. Specifically we formally prove that the sub-carrier resource allocation problem is NP-hard for both power min-imization as well as rate maximization in both uplink and downlink scenarios. More importantly, we also provide in-approximability results for these scenarios, outlining a hard limit on what deterministic allocation algorithms can achieve for this class of problems. While these results are mostly of a negative nature, we also propose a class of heuristics, called k-interchange, which are shown to yield close to optimal performance via simulations