Multi-carrier wireless systems have become a promising means of achieving the high data rates required by emerging wireless applications, especially when combined with link adaptation. Link Adaptation (LA) loosely refers to changing transmission parameters over a link, such as modulation, coding rate, power, etc., in response to changing channel conditions. The adaptation of the transmission parameters is performed according to the predicted future quality of the channel, also called as the channel-state. We assume that each channel (sub-carrier) may be in one of M different states at any given time, with each state corresponding to a different pre-determined data rate achievable through LA. The presence of multiple carriers, combined with LA, leads to the possibility of choosing which sub-carriers to use, and at what rate to transmit on each sub-carrier in each time-slot.