Informace o publikaci
Minimizing Expected Termination Time in One-Counter Markov Decision Processes
| Autoři | |
|---|---|
| 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 | |
| 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: |