Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

BRÁZDIL Tomáš KUČERA Antonín NOVOTNÝ Petr WOJTCZAK Dominik

Rok publikování 2012
Druh Článek ve sborníku
Konference Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-642-31585-5_16
Obor Informatika
Klíčová slova one-counter automata; markov decision processes
Přiložené soubory
Popis V článku se zabýváme problémem minimalizace času ukončení výpočtu v Markovových rozhodovacích procesech s jedním čítačem. Prezentujeme algoritmus s exponenciální časovou složitostí, který pro libovolné zadané e>0 aproximuje (s přesností e) optimální hodnotu času ukončení v zadané počáteční konfiguraci, a zároveň vypočítá příslušnou e-optimální strategii. Rovněž ukazujeme, že za předpokladu nerovnosti tříd P a NP nemůže pro tyto problémy existovat polynomiální algoritmus.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.