Combinatorial structure and randomized subexponential algorithms for infinite games

DOI10.1016/j.tcs.2005.07.041zbMath1086.68085OpenAlexW2155388558MaRDI QIDQ817809

Henrik Björklund, Sergei Vorobyov

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.041

zbMATH Keywords

parity gamesrandomized algorithmspseudo-Boolean optimizationmean payoff gamescombinatorial linear programmingcompletely unimodal functionssimple stochastic games

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15) Specification and verification (program logics, model checking, etc.) (68Q60) Randomized algorithms (68W20)

Related Items (14)

Parity game reductions ⋮ A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Fixpoint Theory -- Upside Down ⋮ Continuous Positional Payoffs ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Fixpoint theory -- upside down ⋮ Cyclic games and linear programming ⋮ Automatizability and Simple Stochastic Games ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ Mean-payoff games and propositional proofs ⋮ Unnamed Item ⋮ The GKK algorithm is the fastest over simple mean-payoff games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-Boolean optimization
• Completely unimodal numberings of a simple polytope
• Positional strategies for mean payoff games
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Linear programming, the simplex algorithm and simple polytopes
• Memoryless determinacy of parity and mean payoff games: a simple proof
• A subexponential randomized algorithm for the simple stochastic game problem
• A subexponential bound for linear programming
• Finite state Markovian decision processes
• Mean Cost Cyclical Games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Low order polynomial bounds on the expected performance of local improvement algorithms
• A combinatorial bound for linear programming and related problems
• Algorithms, games, and the internet
• Mathematical Foundations of Computer Science 2004
• On Nonterminating Stochastic Games
• Stochastic Games
• Perspectives of System Informatics

This page was built for publication: Combinatorial structure and randomized subexponential algorithms for infinite games