Efficient Computation of a Canonical Form for a Generalized P-matrix

Abstract

We use recent results on algorithms for Markov decision problems to show that a canonical form for a generalized P-matrix can be computed, in some important cases, by a strongly polynomial algorithm.

References in corpus (1)

• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

Cited by in corpus (1)

• A Strongly Polynomial Reduction for Linear Programs over Grids