A subexponential lower bound for the random facet algorithm for parity games

MaRDI QIDQ5365038zbMATH OpenFDO

Authors Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133055

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Linear programming (90C05) Noncooperative games (91A10)

Recommendations

• A Deterministic Subexponential Algorithm for Solving Parity Games
• A randomized subexponential algorithm for parity games
• scientific article; zbMATH DE number 1962853
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

Cited in

(12)

• A sublinear-time randomized approximation algorithm for matrix games
• Unique end of potential line
• A randomized subexponential algorithm for parity games
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• The mu-calculus and Model Checking
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• The complexity of all-switches strategy improvement
• A parity game tale of two counters
• Unique End of Potential Line
• An exponential lower bound for Zadeh's pivot rule
• An unconditional lower bound for the active-set method on the hypercube

This page was built for publication: A subexponential lower bound for the random facet algorithm for parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365038)