Linear Programming Polytope and Algorithm for Mean Payoff Games

DOI10.1007/11775096_8MaRDI QIDQ5434383zbMATH OpenOpenAlexFDO

Authors Ola Svensson, Sergei Vorobyov

Publication date 4 January 2008

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11775096_8

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) Games involving graphs (91A43)

Recommendations

• Combinatorial simplex algorithms can solve mean payoff games
• From Parity and Payoff Games to Linear Programming
• On solving mean payoff games using pivoting algorithms
• The complexity of mean payoff games on graphs
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average

Cited in

(9)

• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
• From Parity and Payoff Games to Linear Programming
• LINEAR PROGRAMMING TECHNIQUE TO SOLVE TWO PERSON MATRIX GAMES WITH INTERVAL PAY-OFFS
• Tropical linear-fractional programming and parametric mean payoff games
• On solving mean payoff games using pivoting algorithms
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
• Combinatorial simplex algorithms can solve mean payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Cyclic games and linear programming

This page was built for publication: Linear Programming Polytope and Algorithm for Mean Payoff Games

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