Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00057577" target="_blank" >RIV/00216224:14330/12:00057577 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-31585-5_16" target="_blank" >http://dx.doi.org/10.1007/978-3-642-31585-5_16</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-31585-5_16" target="_blank" >10.1007/978-3-642-31585-5_16</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Popis výsledku v původním jazyce
We consider the problem of computing the value and an optimal strategy for minimizing the expected termination time in one-counter Markov decision processes. Since the value may be irrational and an optimal strategy may be rather complicated, we concentrate on the problems of approximating the value up to a given error epsilon > 0 and computing a finite representation of an epsilon-optimal strategy. We show that these problems are solvable in exponential time for a given configuration, and we also show that they are computationally hard in the sense that a polynomial-time approximation algorithm cannot exist unless P=NP.
Název v anglickém jazyce
Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Popis výsledku anglicky
We consider the problem of computing the value and an optimal strategy for minimizing the expected termination time in one-counter Markov decision processes. Since the value may be irrational and an optimal strategy may be rather complicated, we concentrate on the problems of approximating the value up to a given error epsilon > 0 and computing a finite representation of an epsilon-optimal strategy. We show that these problems are solvable in exponential time for a given configuration, and we also show that they are computationally hard in the sense that a polynomial-time approximation algorithm cannot exist unless P=NP.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2012
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)
ISBN
9783642315848
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
12
Strana od-do
141-152
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Warwick
Datum konání akce
1. 1. 2012
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—