Skip to Main content Skip to Navigation
Journal articles

Tropical linear-fractional programming and parametric mean payoff games

Abstract : 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
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00782737
Contributor : Canimogy Cogoulane Connect in order to contact the contributor
Submitted on : Wednesday, January 30, 2013 - 3:02:18 PM
Last modification on : Monday, March 28, 2022 - 5:08:26 PM

Links full text

Identifiers

Collections

Citation

Stéphane Gaubert, R.D. Katz, S.N. Sergeev. Tropical linear-fractional programming and parametric mean payoff games. Journal of Symbolic Computation, Elsevier, 2012, 47 (12), pp.1447-1478. ⟨10.1016/j.jsc.2011.12.049⟩. ⟨hal-00782737⟩

Share

Metrics

Record views

126