A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
share
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 + nlog 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(mlog m) iterations, improving upon the previous best bound of O(m^2log m) by Wang et al. (2006).
READ FULL TEXT