On the Complexity of Joint Subcarrier and Power Allocation for Multi-User OFDMA Systems

I. INTRODUCTION

• OFDMA decomposes frequency-selective wideband channels into narrowband subcarriers and uses cyclic redundancy to enable FFT processing and one-tap scalar equalization.This makes the technique suited to frequency-selective channels and high data rates.Source: §I · p. 2
• Fixed, nonoverlapping subcarrier assignments can waste bandwidth when traffic or channel conditions change, motivating dynamic allocation in WiMAX, LTE, and dense femtocell downlinks.OFDMA avoids interference between users on different subcarriers, but preassignment can prevent an unusable subcarrier from being reassigned.Source: §I · pp. 2–3
• Although joint allocation is nonconvex and has inspired heuristic methods,, –, nonconvexity alone does not establish computational intractability.The paper distinguishes its OFDMA-constrained problem from prior dynamic spectrum management results whose hardness analyses depend on crosstalk channel gains,.Source: §I · pp. 3–4
• Both total-power minimization and utility maximization are strongly NP-hard via a polynomial-time transformation from 3-dimensional matching.The result motivates seeking high-quality approximate or locally optimal solutions rather than expecting a polynomial-time method for global optimization in general.Source: §I · p. 4
• With one user, both formulations are polynomial-time solvable; total-power minimization is also polynomial-time solvable when users and subcarriers are equal in number.The paper also identifies subclasses solvable to global or ϵ-global optimality in polynomial time.Source: §I · p. 4
• The paper studies minimizing total transmission power subject to users’ quality-of-service and power constraints, and maximizing sum-rate, proportional-fairness, harmonic-mean, or min-rate utility under per-user power budgets.Both formulations also enforce individual subcarrier power limits and the OFDMA constraint.Source: §I · p. 4

• The model assumes N ≥ K, and the OFDMA constraint permits at most one user to transmit on each subcarrier.Source: §II · pp. 5–6
• The first formulation minimizes total transmission power subject to user rate targets, power budgets, and the OFDMA constraint.Source: §II · p. 6
• Binary variables indicate whether a user occupies a subcarrier; fixing this allocation partitions subcarriers by user and leaves decoupled convex power-allocation problems.The paper describes the joint problem equivalently through compact and intuitive formulations, and bases its analysis mainly on the compact formulation.Source: §II · pp. 6–7
• The second formulation maximizes a system utility under per-user power budgets and the OFDMA constraint; one listed utility is the minimum user rate.Source: §II · p. 7

III. HARD CASES

• Both total-power minimization and system-utility maximization are strongly NP-hard when N/K equals any fixed constant c > 1.The section introduces complexity theory before proving hardness for the two formulations in separate subsections.Source: §III · p. 8

A. A Brief Introduction to Complexity Theory

• A problem is NP-hard if it is at least as hard as every problem in NP, while NP-complete problems are the hardest problems within NP.The 3-colorability problem is given as an NP-complete example.Source: A. A Brief Introduction to Complexity… · p. 8
• Strong NP-hardness additionally rules out pseudo-polynomial-time algorithms; 3-colorability is strongly NP-complete, while partition is NP-hard but not strongly NP-hard.Pseudo-polynomial time may depend polynomially on both input length and numerical data values, unlike polynomial time, which depends only on input length.Source: A. A Brief Introduction to Complexity… · p. 8
• If an optimization problem is NP-hard, polynomial-time global optimization is not expected unless P=NP, motivating high-quality approximate or locally optimal solutions.NP-hard problems need not belong to NP, but are at least as hard as NP-complete problems.Source: A. A Brief Introduction to Complexity… · pp. 8–9
• To prove optimization hardness, it suffices to show its feasibility or decision version is NP-hard, because that version is easier than finding the global optimum and minimizer.The decision version asks whether the global minimum is below a given threshold.Source: A. A Brief Introduction to Complexity… · p. 9
• A standard reduction selects a known NP-complete decision problem, maps its instances to the target in polynomial time, and preserves truth; a strongly NP-complete source yields strong NP-hardness.The following subsections apply this approach to problems (3) and (6).Source: A. A Brief Introduction to Complexity… · p. 9

B. Strong NP-Hardness of Power Minimization Problem (3) when N/K = c > 1

• For c = 2, the reduction maps each 3-dimensional matching instance to a system with K users and 2K subcarriers, preserving feasibility in both directions.The source problem is strongly NP-complete [35], and the transformation is polynomial time.Source: B. Strong NP-Hardness of Power… · pp. 10, 11, 13
• Satisfaction of all users’ transmission rate requirements implies that each user transmits on one subcarrier from {1y, 2y, ..., Ky} with noise power 1 and one from {1z, 2z, ..., Kz} with noise power 2.Source: B. Strong NP-Hardness of Power… · p. 12
• For any constant c > 1, checking feasibility of problem (3) is strongly NP-hard, and thus the optimization problem is strongly NP-hard.The proof establishes the result for feasibility; the section also states that strong NP-hardness of feasibility implies strong NP-hardness of the original optimization problem.Source: B. Strong NP-Hardness of Power… · pp. 9, 13, 14
• Problem (3) remains strongly NP-hard when per-subcarrier power budgets are replaced by either of the stated total-power constraints.The section gives parameter settings for the reduction and states that the same hardness results for problems (3) and (6) hold under either total-power constraint.Source: B. Strong NP-Hardness of Power… · pp. 14–15
• For joint subcarrier-and-bit allocation, prior work established strong NP-hardness when m ≥ 2, and the paper also derives it using the same reduction argument.The result concerns the decision version of the bit-allocation problem.Source: B. Strong NP-Hardness of Power… · p. 15

C. Strong NP-Hardness of Utility Maximization Problem (6) when N/K = c > 1

• Theorem 3.2 shows that, for any constant c > 1, maximizing system utility (6) with H equal to H1, H2, H3, or H4 is strongly NP-hard when N/K = c.Source: C. Strong NP-Hardness of Utility… · p. 16
• Prior work showed sum-rate utility is NP-hard with two users via equipartition, whereas Theorem 3.2 establishes strong NP-hardness.Source: C. Strong NP-Hardness of Utility… · p. 16
• Reference claimed NP-hardness for the other three utilities in the two-user case, but its equipartition-based proof is nonrigorous.A yes-instance does not imply equal transmission rates for the two users at the corresponding utility-maximization solution, or vice versa.Source: C. Strong NP-Hardness of Utility… · p. 16
• For fixed K ≥ 2, the complexity status remains unknown for proportional-fairness, harmonic-mean, and min-rate utility maximization.Source: C. Strong NP-Hardness of Utility… · p. 16
• The proof transforms 3-dimensional matching to decision versions of problems (3) and (6), implying no polynomial-time global optimizer unless P=NP.The paper concludes that approximately optimal subcarrier and power allocation is more realistic in practice.Source: C. Strong NP-Hardness of Utility… · p. 16

• A strong polynomial-time algorithm has dimension-dependent polynomial complexity and solves the problem to global optimality.Source: §IV · p. 16
• With one user, both problem (3) and problem (6) are polynomial-time solvable using (extended) water-filling techniques.The section identifies these as separate subclasses for the two problems.Source: §IV · p. 17
• When the number of subcarriers equals the number of users, problem (3) is strongly polynomial-time solvable as a complete-bipartite-graph assignment problem.The assignment problem can be solved in strong polynomial time.Source: §IV · p. 17
• Problem (6) with sum-rate utility and no total power constraint is polynomial-time solvable by transformation to the Hitchcock problem.Source: §IV · p. 17

A. Polynomial Time Solvability of Problem (3) when K = 1

• Problem (16) and its power-control formulation (17) share the same optimal solution, enabling the derivation of a closed-form solution.For fixed P, (17) is strictly convex and has a unique solution.Source: A. Polynomial Time Solvability of… · pp. 17–18
• The optimal solution is an extended water-filling solution, with λ chosen so that the objective value of (17) equals γ.The extension accounts for per-subcarrier power budgets in addition to the total power constraint.Source: A. Polynomial Time Solvability of… · p. 18
• O(log2(R/ϵ) + N log2(N)) operations suffice in the worst case, so problem (16) is polynomial-time solvable.The search uses the increasing objective in τ = 1/λ and bounds derived by ordering a sequence of values.Source: A. Polynomial Time Solvability of… · pp. 18–19
• The complexity of total-power minimization remains unknown when K ≥ 2 is fixed.Source: A. Polynomial Time Solvability of… · p. 19

• A fixed P in problem (22), unlike the unknown P in problem (17), enables a strong polynomial-time algorithm.Source: B. Strong Polynomial Time Solvability… · p. 19
• The solution uses extended water-filling, choosing τ = 1/λ to satisfy the total-power constraint and finding τ in closed form from a univariate linear equation.Source: B. Strong Polynomial Time Solvability… · p. 20
• Finding the desired τ has complexity O(N log_2(N)).Source: B. Strong Polynomial Time Solvability… · p. 20

C. Strong Polynomial Time Solvability of Problem (3) when N = K

• For N = K, Problem (3) becomes a complete-bipartite assignment problem solvable globally by the Hungarian method in O(K^3) operations.The method also returns a global optimal integer solution to the linear-program relaxation in O(K^3) operations.Source: C. Strong Polynomial Time Solvability… · pp. 20–21
• For N = K + C with fixed C ≥ 1, Problem (3) is solvable in O(K^(2C+3)) operations.The approach partitions the subcarriers into K nonempty subsets, solves an assignment problem for each partition, and selects the best feasible result; the number of partitions is at most (K + C)^(2C).Source: C. Strong Polynomial Time Solvability… · p. 22

V. CONCLUDING REMARKS

• The general joint allocation problem is strongly NP-hard, but is polynomial-time solvable when there is one user or when users and subcarriers are equal in number.The paper therefore argues that globally optimal algorithms for the general case are not feasible unless P=NP.Source: §V · p. 25

PROOF OF THEOREM 3.1

• For c>1, the Theorem 3.1 reduction partitions users and subcarriers into types, using good and bad channel parameters to force type-matched transmissions.Type-II users and subcarriers serve as dummies, reducing feasibility to whether Type-I users can meet their rate targets with twice as many Type-I subcarriers as users.Source: PROOF OF THEOREM 3.1 · p. 26
• The constructed cases force Type-I users to meet their rate targets on Type-I subcarriers, a feasibility check that is strongly NP-hard.In the second case, the single Type-II user must transmit at full power on all Type-II subcarriers.Source: PROOF OF THEOREM 3.1 · pp. 27–28

PROOF OF THEOREM 3.2

• For c = 2, all four utility maximization problems (6) are strongly NP-hard; the reduction makes an optimal value of at least 3 equivalent to a yes-instance of 3-dimensional matching.Source: PROOF OF THEOREM 3.2 · pp. 29–30
• For the general case N/K = c > 1, constructing dummy users and subcarriers as in Theorem 3.1’s proof establishes strong NP-hardness for sum-rate maximization; similar results hold for the other three utility functions.Source: PROOF OF THEOREM 3.2 · p. 30

EXTENDED WATER-FILLING SOLUTION FOR POWER CONTROL PROBLEM (17)

• Convexity makes the KKT conditions necessary and sufficient for problem (17), and the constructed multipliers verify that (18) is its solution.The multipliers are chosen separately for zero, interior, and maximum-power allocations.Source: EXTENDED WATER-FILLING SOLUTION FOR… · pp. 30–31

• S(N, K) counts partitions of N objects into K nonempty subsets, for N ≥ K ≥ 1.The initial conditions are S(k, k) = 1 and S(k, 0) = 0 for k ≥ 1.Source: Appendix D · p. 31
• The Stirling recurrence separates partitions by whether the newest object forms a singleton or joins a nonempty subset.For the induction base, partitioning K + 1 elements into K sets amounts to choosing the two elements in the sole size-2 set.Source: Appendix D · p. 31
• For the stated parameters K and C, the passages establish the upper bound S(K + C, K) ≤ (K + C)^(2C), with the induction conclusion confirming that inequality.Source: Appendix D · pp. 31–32