Before revision:  We extend and strengthen previous work of Madani (2002) that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method for solving deterministic Markov decision processes (DMDPs) , a special class of 2VPI linear programs .
After revision:  We extend and strengthen previous work of Madani (2002) that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method for solving deterministic Markov decision processes (DMDPs) , a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains: (i) For linear fractional combinatorial optimization, we show a convergence bound of O(m \log m) iterations; the previous best bound was O(m^2 \log m) by Wang et al. (2006). (ii) We obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI) .