A highly efficient decoding algorithm for the REMOS (REverberation MOdeling for Speech recognition) concept for distant-talking speech recognition as proposed in [1] is suggested to reduce the computational complexity by about two orders of magnitude and thereby allowing for first real-time implementations. REMOS is based on a combined acoustic model consisting of a conventional hidden Markov model (HMM), modeling the clean speech, and a reverberation model. During recognition, the most likely clean-speech and reverberant contributions are estimated by solving an inner optimization problem for logarithmic melspectral (log-melspec) features. In this paper, two approximation techniques for the inner optimization problem are derived. Connected digit recognition experiments confirm that the computational complexity is significantly reduced. Ensuring that the global optima of the inner optimization problem are found, the decoding algorithm based on the proposed approximations even increases the recognition accuracy relative to interior point optimization techniques.