Orthogonal frequency-division multiplexing (OFDM) modulation can be utilized to deal with severe channel conditions without complex equalization. However, in a fast-fading channel, Doppler spread caused by user mobility destroys the orthogonality among subcarriers, prompting intercarrier interference (ICI). In this paper, the OFDM ICI reduction problem is formulated as a combinatorial optimization problem. Two relaxation methods are proposed to relax the maximum-likelihood detection problem into convex quadratic programming (QP) problems. To further reduce computational complexity, the QP problems are solved by limiting the search to the two-dimensional subspace. A low-bit descent search can also be employed to improve the system performance. The extension to higher-order quadrature amplitude modulation (QAM) OFDM systems is also addressed. Performance results are given which demonstrate that the integer QP relaxation-based algorithms provide excellent performance with reasonable computational complexity.