Before revision:  Every iteration takes O(  m + n \log n) time for DMDPs, and O(mn) time for general 2VPI systems. The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm.
After revision:  Every iteration takes O( m + n \log n) time for the special case of deterministic Markov Decision Processes (DMDPs). This extends and strengthens a previous result by Madani (2002) that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm.