A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes
From MaRDI portal
Publication:5363381
DOI10.1137/16M105678XzbMath1378.68074MaRDI QIDQ5363381
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Publication date: 6 October 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
computational complexityNewton's methodpolynomial-time algorithmsnonlinear systems of equationsmultitype branching processesextinction probabilities
Analysis of algorithms and problem complexity (68Q25) General theory of stochastic processes (60G07) Grammars and rewriting systems (68Q42) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithmic approach to the extinction probability of branching processes
- Newton's iteration for the extinction probability of a Markovian binary tree
- Markovian trees: Properties and algorithms
- A tutorial on geometric programming
- On the link between Markovian trees and tree-structured Markov chains
- Geometric algorithms and combinatorial optimization.
- Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes
- Random walks with ``back buttons
- Solving nonlinear matrix equations arising in tree-like stochastic processes.
- Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
- Model Checking of Recursive Probabilistic Systems
- Computing the Least Fixed Point of Positive Polynomial Systems
- On the Complexity of Nash Equilibria and Other Fixed Points
- COMPUTING LEAST FIXED POINTS OF PROBABILISTIC SYSTEMS OF POLYNOMIALS
- Extinction Probabilities of Supercritical Decomposable Branching Processes
- Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata
- A Structured Markov Chain Approach to Branching Processes
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
- On the Complexity of Numerical Analysis
- Matrix Analysis
- Biological Sequence Analysis
- Introduction to Matrix Analytic Methods in Stochastic Modeling
- Branching Processes
- Model Checking Probabilistic Pushdown Automata
- Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
- Exact algorithms for solving stochastic games
- Numerical Methods for Structured Markov Chains
- Branching processes in biology