Sökning: onr:"swepub:oai:DiVA.org:miun-50959" >
Fast Algorithms for...
-
Andersson, DanielUppsala universitet,Institutionen för informationsteknologi,Datalogi
(författare)
Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality
Förlag, utgivningsår, omfång ...
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:uu-18825
-
https://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-18825URI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:vet swepub-contenttype
-
Ämneskategori:rap swepub-publicationtype
Anmärkningar
-
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.
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Vorobyov, SergeiUppsala universitet,Institutionen för informationsteknologi,Datalogi
(författare)
-
Uppsala universitetInstitutionen för informationsteknologi
(creator_code:org_t)
Internetlänk