. "10.1007/978-3-642-31585-5_16" . "150658" . . "Minimizing Expected Termination Time in One-Counter Markov Decision Processes" . "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."@en . "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." . "Wojtczak, Dominik" . "Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)" . . "[BB9CD208EA48]" . . . "Minimizing Expected Termination Time in One-Counter Markov Decision Processes"@en . "2012-01-01+01:00"^^ . . "P(GAP202/10/1469), P(GPP202/12/P612)" . . "12"^^ . . . "Warwick" . . "one-counter automata; markov decision processes"@en . . "Ku\u010Dera, Anton\u00EDn" . "14330" . "4"^^ . "3"^^ . "0302-9743" . . . "Minimizing Expected Termination Time in One-Counter Markov Decision Processes" . . "Novotn\u00FD, Petr" . "RIV/00216224:14330/12:00057577" . "9783642315848" . "Berlin" . "Br\u00E1zdil, Tom\u00E1\u0161" . "Minimizing Expected Termination Time in One-Counter Markov Decision Processes"@en . . . . "RIV/00216224:14330/12:00057577!RIV13-GA0-14330___" . . "Springer-Verlag" . .