Combinatorial structure and randomized subexponential algorithms for infinite games

DOI10.1016/J.TCS.2005.07.041zbMATH Open1086.68085OpenAlexW2155388558MaRDI QIDQ817809FDOQ817809

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

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

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)

Cites Work

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

Cited In (19)

• Continuous Positional Payoffs
• Fixpoint Theory -- Upside Down
• Constraint Satisfaction Problems over Numeric Domains
• Cyclic games and linear programming
• Automatizability and Simple Stochastic Games
• Mean-payoff games and propositional proofs
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• Thick Subtrees, Games and Experiments
• A randomized subexponential algorithm for parity games
• Fixpoint theory -- upside down
• A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
• Parity game reductions
• Gillies and Miller's Subrelations of a Relation over an Infinite Set of Alternatives: General Results and Applications to Voting Games
• Title not available (Why is that?)
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Title not available (Why is that?)
• A nested family of \(k\)-total effective rewards for positional games
• The GKK algorithm is the fastest over simple 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)