  Optimal channel allocation is a key performance engineering aspect in
single-carrier frequency-division multiple access (SC-FDMA). It is of
significance to consider minimum sum power (Min-Power), subject to meeting
specified user's demand, since mobile users typically employ battery-powered
handsets. In this paper, we prove that Min-Power is polynomial-time solvable
for interleaved SC-FDMA (IFDMA). Then we propose a channel allocation algorithm
for IFDMA, which is guaranteed to achieve global optimum in polynomial time. We
numerically compare the proposed algorithm with optimal localized SC-FDMA
(LFDMA) for Min-Power. The results show that LFDMA outperforms IFDMA in the
maximal supported user demand. When the user demand can be satisfied in both
LFDMA and IFDMA, LFDMA performs slightly better than IFDMA. However Min- Power
is polynomial-time solvable for IFDMA whereas it is not for LFDMA.
