Certain embodiments of the present disclosure may allow WiMAX signaling overhead to be reduced by sending burst allocation information to MSs using messages that may be transmitted using more efficient modulation coding schemes (MCSs) than that allowed for DL-MAP and UL-MAP messages. For example, burst allocation information may be sent in SUB-DL-UL-MAP or HARQ-MAP messages that may be encoded with selectable MCSs that result in higher data rate than an MCS used for conventional DL-MAP and UL-MAP messages. For certain embodiments, MSs may be partitioned into groups based on CINR and the burst allocation information for each group may be transmitted using an MCS that is appropriate for that group based on the CINR for MSs in that group.