A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions (Q2417852): Difference between revisions

← Older edit

@@ aliases / en / 0 / aliases / en / 0 @@
+A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 6195427
@@ Property / title @@
+A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions (English)
+Normal rank
@@ Property / zbMATH Open document ID @@
+.91016
@@ Property / zbMATH Open document ID: 1336.91016 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/978-3-642-39206-1_19
@@ Property / DOI: 10.1007/978-3-642-39206-1_19 / rank @@
+Normal rank
@@ Property / author @@
+Khaled M. Elbassioni
@@ Property / author: Khaled M. Elbassioni / rank @@
+Normal rank
@@ Property / author @@
+Vladimir A. Gurvich
@@ Property / author: Vladimir A. Gurvich / rank @@
+Normal rank
@@ Property / published in @@
+Automata, Languages, and Programming
@@ Property / published in: Automata, Languages, and Programming / rank @@
+Normal rank
@@ Property / publication date @@
+August 2013Timestamp +2013-08-06T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2013-08-06T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 6 August 2013 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+A05
@@ Property / Mathematics Subject Classification ID: 91A05 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+A43
@@ Property / Mathematics Subject Classification ID: 91A43 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6195427
@@ Property / zbMATH DE Number: 6195427 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2923722914
@@ Property / OpenAlex ID: W2923722914 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1780290573
@@ Property / OpenAlex ID: W1780290573 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.03431
@@ Property / arXiv ID: 1508.03431 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Solving Stochastic Games on Graphs
+Normal rank
@@ Property / cites work @@
+Combinatorial structure and randomized subexponential algorithms for infinite games
+Normal rank
@@ Property / cites work @@
+A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
+Normal rank
@@ Property / cites work @@
+Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
+Normal rank
@@ Property / cites work @@
+A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
+Normal rank
@@ Property / cites work @@
+On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
+Normal rank
@@ Property / cites work @@
+On canonical forms for zero-sum stochastic mean payoff games
+Normal rank
@@ Property / cites work @@
+Reduction of stochastic parity to stochastic mean-payoff games
+Normal rank
@@ Property / cites work @@
+Q5501249
@@ Property / cites work: Q5501249 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4633826
@@ Property / cites work: Q4633826 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of stochastic games
@@ Property / cites work: The complexity of stochastic games / rank @@
+Normal rank
@@ Property / cites work @@
+Q4287357
@@ Property / cites work: Q4287357 / rank @@
+Normal rank
@@ Property / cites work @@
+Another sub-exponential algorithm for the simple stochastic game
+Normal rank
@@ Property / cites work @@
+Positional strategies for mean payoff games
@@ Property / cites work: Positional strategies for mean payoff games / rank @@
+Normal rank
@@ Property / cites work @@
+Q3245641
@@ Property / cites work: Q3245641 / rank @@
+Normal rank
@@ Property / cites work @@
+Simple Stochastic Games with Few Random Vertices Are Easy to Solve
+Normal rank
@@ Property / cites work @@
+Cyclic games and an algorithm to find minimax cycle means in directed graphs
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2004
@@ Property / cites work: Mathematical Foundations of Computer Science 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
+Normal rank
@@ Property / cites work @@
+Solving Simple Stochastic Games with Few Coin Toss Positions
+Normal rank
@@ Property / cites work @@
+Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
+Normal rank
@@ Property / cites work @@
+Q2763539
@@ Property / cites work: Q2763539 / rank @@
+Normal rank
@@ Property / cites work @@
+A deterministic subexponential algorithm for solving parity games
+Normal rank
@@ Property / cites work @@
+A characterization of the minimum cycle mean in a digraph
+Normal rank
@@ Property / cites work @@
+Cyclical games with prohibitions
@@ Property / cites work: Cyclical games with prohibitions / rank @@
+Normal rank
@@ Property / cites work @@
+Stochastic Games with Perfect Information and Time Average Payoff
+Normal rank
@@ Property / cites work @@
+Q5611539
@@ Property / cites work: Q5611539 / rank @@
+Normal rank
@@ Property / cites work @@
+Extensions of two person zero sum games
@@ Property / cites work: Extensions of two person zero sum games / rank @@
+Normal rank
@@ Property / cites work @@
+Mean Cost Cyclical Games
@@ Property / cites work: Mean Cost Cyclical Games / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms for stochastic games ? A survey
@@ Property / cites work: Algorithms for stochastic games ? A survey / rank @@
+Normal rank
@@ Property / cites work @@
+Cyclic games and linear programming
@@ Property / cites work: Cyclic games and linear programming / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of mean payoff games on graphs
@@ Property / cites work: The complexity of mean payoff games on graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
+Normal rank
@@ Property / cites work @@
+Polynomial-time algorithms for energy games with special weight structures
+Normal rank
@@ Property / cites work @@
+Q4275381
@@ Property / cites work: Q4275381 / rank @@
+Normal rank
@@ Property / cites work @@
+New Results on Simple Stochastic Games
@@ Property / cites work: New Results on Simple Stochastic Games / rank @@
+Normal rank
@@ Property / cites work @@
+A convex programming-based algorithm for mean payoff stochastic games with perfect information
+Normal rank
@@ Property / cites work @@
+Boundary Theory for Recurrent Markov Chains
@@ Property / cites work: Boundary Theory for Recurrent Markov Chains / rank @@
+Normal rank
@@ Property / cites work @@
+A criterion and verification of the ergodicity of cyclic game forms
+Normal rank
@@ Property / cites work @@
+A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
+Normal rank
@@ Property / cites work @@
+A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / Wikidata QID @@
+Q128185774
@@ Property / Wikidata QID: Q128185774 / rank @@
+Normal rank

Latest revision as of 23:16, 1 August 2024

scientific article; zbMATH DE number 6195427

A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions

Language	Label	Description	Also known as
English	A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions	scientific article; zbMATH DE number 6195427	A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions