Tropical convexity applied to dynamic programming : a guided tour

Abstract

Tropical convex sets have arisen in various guises. They can be obtained as limits of classical polyhedra, or as images by the valuation of polyhedra over the field of Puiseux series. We shall review some basic problems and results in tropical convexity, emphasizing the application to dynamic programming. These include external representation (separation and projection), discrepancies between classical and tropical vertices, and the equivalence between tropical linear programming and mean payoff games. Several of these results rely on techniques of non-linear Perron Frobenius theory.