Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality
2006 (English)Report (Other scientific)
We suggest new strongly polynomial algorithms for solving linear programs
min( \Sigma x_i |S ) with constraints S of the monotonic discounted form x_i ≥ λx_j + β with 0 < λ < 1. The algorithm for the case when the discounting factor λ is equal for all constraints is O(mn2 ), whereas the algorithm for the case when λ may vary between the constraints is O(mn2 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.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:uu:diva-18825OAI: oai:DiVA.org:uu-18825DiVA: diva2:46597