  Uplink scheduling/resource allocation under the single-carrier FDMA
constraint is investigated, taking into account the queuing dynamics at the
transmitters. Under the single-carrier constraint, the problem of MaxWeight
scheduling, as well as that of determining if a given number of packets can be
served from all the users, are shown to be NP-complete. Finally, a
matching-based scheduling algorithm is presented that requires only a
polynomial number of computations per timeslot, and in the case of a system
with large bandwidth and user population, provably provides a good delay
(small-queue) performance, even under the single-carrier constraint.
  In summary, the results in first part of the paper support the recent push to
remove SCFDMA from the Standards, whereas those in the second part present a
way of working around the single-carrier constraint if it remains in the
Standards.
