Before revision:  The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm. This also leads to an acceleration of the Newton-Dinkelbach method for general fractional combinatorial optimization problems. For the special case of linear fractional combinatorial optimization, our method converges in O(m\log m) iterations, improving upon the previous best bound of O(m^2\log m) by Wang et al. ( 2006 ).
After revision:  The key technical idea is a new analysis of the Newton-Dinkelbach method for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result by Goemans et al. ( 2006 ).