Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality
Daniel Andersson, Sergei G. Vorobyov · 2006
We suggest new strongly polynomial algorithms for solving linear programs min ( � xi|S) with constraints S of the monotonic discounted form xi ≥ λxj + β with 0 < λ < 1. The algorithm for the case when the discounting factor λ is equal for all constraints is O(mn 2), whereas the algorithm for the case when λ may vary between the constraints is O(mn 2 log m), where n is the number of variables and m is the number of constraints. As applications, we obtain the best currently available algorithm for two-player discounted payoff games and a new faster strongly subexponential algorithm for the ergodic partition problem for mean payoff games. 1