An Interval Assignment Problem for Resource Optimization in LTE Networks

In this paper we study the problem of resource allocation in SC-FDMA (Single Carrier Frequency Division Multiple Access) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE (3rd Generation Partnership Project - Long Term Evolution) standard. The problem can be modeled as an assignment problem where each user can be given a subset of consecutive channels seen as an interval. After introducing the problem, we first prove that it is NP-hard to solve. Then we review some cases where the problem is solvable in polynomial time. An efficient cutting plane algorithm is presented with experimental results.