Informace o publikaci

Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Autoři

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

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 Rektorát Středisko pro pomoc studentům se specifickými nároky

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
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.

Další info