Registered Data

[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.
  • Classification : 14T90, 91A25, 91B26
  • Format : Talk at Waseda University
  • Author(s) :
    • Omar Saadi (College of Computing, Mohammed VI Polytechnic University)
    • Marianne Akian (INRIA and CMAP, École polytechnique)
    • Stéphane Gaubert (INRIA and CMAP, École polytechnique)
    • Yang Qi (INRIA and CMAP, École polytechnique)