Combinatorial structure and randomized subexponential algorithms for infinite games

DOI10.1016/J.TCS.2005.07.041MaRDI QIDQ817809zbMATH OpenOpenAlexFDO

Authors 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

randomized algorithmsparity gamespseudo-Boolean optimizationmean payoff gamescombinatorial linear programmingcompletely unimodal functionssimple stochastic games

Mathematics Subject Classification ID

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

Recommendations

• A randomized subexponential algorithm for parity games
• Subexponential algorithms for unique games and related problems
• scientific article; zbMATH DE number 3952008
• A subexponential randomized algorithm for the simple stochastic game problem
• scientific article; zbMATH DE number 1953100
• Linear complementarity algorithms for infinite games
• Submodularity of some classes of the combinatorial optimization games
• The complexity of infinitely repeated alternating move games
• scientific article; zbMATH DE number 1342211

Cites work

• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 4004228 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1059247 (Why is no real title available?)
• scientific article; zbMATH DE number 1082101 (Why is no real title available?)
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• A combinatorial bound for linear programming and related problems
• A subexponential bound for linear programming
• A subexponential randomized algorithm for the simple stochastic game problem
• Algorithms, games, and the internet
• Completely unimodal numberings of a simple polytope
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Finite state Markovian decision processes
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
• Linear programming, the simplex algorithm and simple polytopes
• Low order polynomial bounds on the expected performance of local improvement algorithms
• Mathematical Foundations of Computer Science 2004
• Mean cost cyclical games
• Memoryless determinacy of parity and mean payoff games: a simple proof
• On Nonterminating Stochastic Games
• Perspectives of System Informatics
• Positional strategies for mean payoff games
• Pseudo-Boolean optimization
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Stochastic Games
• The complexity of mean payoff games on graphs
• The complexity of stochastic games

Cited in

(18)

• Thick Subtrees, Games and Experiments
• The GKK algorithm is the fastest over simple mean-payoff games
• scientific article; zbMATH DE number 6490915 (Why is no real title available?)
• A subexponential lower bound for the random facet algorithm for parity games
• Cyclic games and linear programming
• Parity game reductions
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• A randomized subexponential algorithm for parity games
• Gillies and Miller's Subrelations of a Relation over an Infinite Set of Alternatives: General Results and Applications to Voting Games
• Automatizability and simple stochastic games
• Constraint satisfaction problems over numeric domains
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Mean-payoff games and propositional proofs
• Fixpoint Theory -- Upside Down
• A nested family of \(k\)-total effective rewards for positional games
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• Fixpoint theory -- upside down
• A faster deterministic exponential time algorithm for energy games and mean payoff games

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

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