We present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality (2VPI). 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 . For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. 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. 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 ).
We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method , 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) . For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. Every iteration takes O( mn) time for general 2VPI systems, and 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 for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result by Goemans et al. ( 2017 ).
R
a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality (2VPI). The algorithm is based on
an accelerated, or 'look-ahead' version of
D
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)
R
special class of 2VPI linear programs
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)
A
mn) time for general 2VPI systems, and O(
R
DMDPs, and O(mn) time for general 2VPI systems. The key technical idea is a new analysis
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
R
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
for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result by Goemans
R
2006
2017