Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality

Andersson, DanielUppsala universitet,Institutionen för informationsteknologi,Datalogi (författare)

We suggest new strongly polynomial algorithms for solving linear programsmin( \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 forthe ergodic partition problem for mean payoff games.

Vorobyov, SergeiUppsala universitet,Institutionen för informationsteknologi,Datalogi (författare)
Uppsala universitetInstitutionen för informationsteknologi (creator_code:org_t)

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.