A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes
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 (2)
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
This page was built for publication: A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes
