Mathematics – Metric Geometry
Scientific paper
2011-01-18
Mathematics
Metric Geometry
34 pages, 9 figures, minor corrections, additions and improvements
Scientific paper
10.1016/j.jsc.2011.12.049
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.
Gaubert Stephane
Katz Ricardo D.
Sergeev Sergei
No associations
LandOfFree
Tropical linear-fractional programming and parametric mean payoff games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Tropical linear-fractional programming and parametric mean payoff games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tropical linear-fractional programming and parametric mean payoff games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-286879