<link rel="stylesheet" href="/res/styles.39be4579664c3a48.css">
Artículo

Tropical linear-fractional programming and parametric mean payoff games

Gaubert, Stéphane ; Katz, Ricardo David Icon; Sergeev, Serge

Otros responsables

Fecha

12/2012

Editorial

Academic Press Ltd - Elsevier Science Ltd

Revista

Journal Of Symbolic Computation

Título del libro

Nombre del evento

Fecha del evento

Institución organizadora

ISSN

0747-7171

eISSN

ISBN

Idioma

Inglés

Tipo del evento

Clasificación temática

Resumen

Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the tropical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.

Aprobación

Revisión

Complementado por

Referenciado por

Licencia Creative Commons

Excepto donde se indique lo contrario, la licencia de este ítem se describe como by-nc-sa