Before revision:  The algorithm is based on the Newton-Dinkelbach method for fractional combinatorial optimization . 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:  The algorithm is based on the Newton-Dinkelbach method , a special class of 2VPI linear programs .