4 papers
Ample sets in Cartesian products
Victor Chepoi, Matthew Maat
Ample sets of hypercubes, introduced by A. Dress in 1995, constitute a combinatorial structure with rich properties and important examples. Ample sets can be characterized in a mul…
Lower bounds for ranking-based pivot rules
Yann Disser, Georg Loho, Matthew Maat +1
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games ea…
Strategy Improvement, the Simplex Algorithm and Lopsidedness
Matthew Maat
The strategy improvement algorithm for mean payoff games and parity games is a local improvement algorithm, just like the simplex algorithm for linear programs. Their similarity ha…
Cycle Patterns and Mean Payoff Games
Georg Loho, Matthew Maat, Mateusz Skomra
We introduce the concept of a \emph{cycle pattern} for directed graphs as functions from the set of cycles to the set . The key example for such a pattern is derived fro…