Главная

Kousha Etessami

  1. Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations.

    Чт, 02/23/2012 - 15:01 — SomNambul
    Authors: Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
    Subjects: Computational Complexity
    Abstract

    We show that one can approximate the least fixed point solution for a
    multivariate system of monotone probabilistic max(min) polynomial equations,
    referred to as maxPPSs (and minPPSs, respectively), in time polynomial in both
    the encoding size of the system of equations and in log(1/epsilon), where
    epsilon > 0 is the desired additive error bound of the solution.

  2. One-Counter Markov Decision Processes.

    Пнд, 09/14/2009 - 09:02 — SomNambul
    Authors: Tomáš Brázdil, Václav Brožek, Kousha Etessami, Antonín Kučera, Dominik Wojtczak
    Subjects: Computer Science and Game Theory
    Abstract

    We study the computational complexity of central analysis problems for
    One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented,
    countable-state MDPs. OC-MDPs are equivalent to a controlled extension of
    (discrete-time) Quasi-Birth-Death processes (QBDs), a stochastic model studied
    heavily in queueing theory and applied probability. They can thus be viewed as
    a natural ``adversarial'' version of a classic stochastic model. Alternatively,
    they can also be viewed as a natural probabilistic/controlled extension of
    classic one-counter automata.

Math-arch

RSS-материал