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)

zbMATH Keywords

computational complexityNewton's methodpolynomial-time algorithmsnonlinear systems of equationsmultitype branching processesextinction probabilities

Mathematics Subject Classification ID

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