[00459] Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria
Session Time & Room : 2E (Aug.22, 17:40-19:20) @G304
Type : Contributed Talk
Abstract : We study a tropical linear regression problem consisting in finding a best approximation of a set of points by a tropical hyperplane. We establish a strong duality theorem, showing that the value of this problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron. We show that this problem is polynomial-time equivalent to mean payoff games. We illustrate our results by solving an inverse problem from auction theory.
