Abstract: Orthogonal frequency division multiple access (OFDMA) is a promising candidate for high-speed wireless communication networks, due to its high spectral efficiency and resistance to multipath fading. Fairness and efficiency are two crucial issues in resource allocation for OFDMA wireless networks. The objective of this paper is to provide the required Quality-of-Service (QoS) of the guaranteed performance users with given data rate requirements and to maximize the capacity of the best effort users while maintaining max-min fairness among them. The resource allocation issue in OFDMA systems is the joint optimization of subcarrier assignment and power allocation subject to a total network power constraint. It is a mixed discrete programming issue known to be NP-hard and obtaining an exhaustive search allocation is computationally very expensive. In this paper, the algorithm to solve this non-convex problem is proposed by Lagrangian dual relaxation and obtains the optimal dual point based on the modified ellipsoid method. The algorithm has the polynomial complexity linear with the number of subcarriers. Numerical results show that the proposed algorithm can be near optimal to the globally optimal solutions in terms of both QoS satisfaction and services max-min fairness.