Cyclic games and linear programming
From MaRDI portal
Publication:944703
DOI10.1016/j.dam.2008.04.012zbMath1142.91310OpenAlexW1999183059MaRDI QIDQ944703
Publication date: 10 September 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.012
local searchmean payoffparityiterative improvementsubexponential algorithmscombinatorial linear programmingcontrolled linear programmingdiscounted payoff gamesgeneralized linear complementaritylongest-shortest pathssimple stochastic
Linear programming (90C05) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Combinatorial games (91A46)
Related Items
An average polynomial algorithm for solving antagonistic games on graphs ⋮ 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 ⋮ On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games ⋮ Nash-solvable two-person symmetric cycle game forms ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cyclical games with prohibitions
- Combinatorial structure and randomized subexponential algorithms for infinite games
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- On short paths interdiction problems: Total and node-wise limited interdiction
- Completely unimodal numberings of a simple polytope
- Positional strategies for mean payoff games
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- The complexity of stochastic games
- Extensions of two person zero sum games
- The P-matrix problem is co-NP-complete
- The complexity of mean payoff games on graphs
- Linear programming, the simplex algorithm and simple polytopes
- The generalized linear complementarity problem: Least element theory and Z-matrices
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Memoryless determinacy of parity and mean payoff games: a simple proof
- Existence and uniqueness of solutions for the generalized linear complementarity problem
- A subexponential bound for linear programming
- Mean Cost Cyclical Games
- Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- A deterministic subexponential algorithm for solving parity games
- From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
- Maximizing the minimum source-sink path subject to a budget constraint
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- Shortest-path network interdiction
- Linear Programming Polytope and Algorithm for Mean Payoff Games
- Fundamentals of Computation Theory
- On Nonterminating Stochastic Games
- A generalization of the linear complementarity problem
- Stochastic Games
