The institute of electrical and electronics engineers (IEEE) 802.16e is designed to support a wide range of applications with various quality of service requirements. Since MAP signaling overhead can unacceptably be large for voice traffic, IEEE 802.16e suggests the use of multicast sub-MAPs whose messages are encoded according to the channel condition. In this case, it is desirable for the base station to properly choose a modulation and coding set associated with the channel condition. In this letter, we consider the use of an adaptive modulation coding scheme for the multicast sub-MAPs without explicit information on the channel condition. The proposed scheme can achieve the same MAP coverage as the broadcast MAP while minimizing the signaling overhead. Simulation results show that when it is applied to voice-over-internet protocol (VoIP) services, the proposed scheme can significantly enhance the VoIP capacity.