Howard's multichain policy iteration algorithm for max-plus linear maps

I wrote a C-program which implements Howard's mulichain policy iteration algorithm for max-plus linear maps. It solves the general ``maximal circuit mean'' problem, in directed graphs.

The basic version of the algorithm takes as input a weighted directed graph (or sparse matrix) and returns two vectors: the cycle time, and the bias (which is an eigenvector when the matrix is irreducible). An extended version takes as input a digraph with two valuations, in order to compute the generalized maximal ``weight to length'' circuit mean (the lengths need not be 1).

Howard's algorithm runs in an almost linear time (although no proof of this fact exists). It is much faster than the classical algorithms to compute the cycle time, including Karp's. An implementation of Karp's algorithm is included for comparison.


S. Gaubert Updated Jul 2008