Tropical linear-fractional programming and parametric mean payoff games

DOI10.1016/j.jsc.2011.12.049zbMath1270.90081arXiv1101.3431OpenAlexW2088418904MaRDI QIDQ435971

Stéphane Gaubert, Ricardo D. Katz, Sergey M. Sergeev

Publication date: 13 July 2012

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.3431

zbMATH Keywords

Lagrange multiplierslinear programmingoptimal strategiesNewton iterationstropical algebralinear-fractional programmingmean payoff games

Mathematics Subject Classification ID

Fractional programming (90C32) 2-person games (91A05)

Related Items (24)

Algebraic solutions of tropical optimization problems ⋮ Tropicalizing the Simplex Algorithm ⋮ The level set method for the two-sided max-plus eigenproblem ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ Solution of a tropical optimization problem with linear constraints ⋮ Max-plus approximation for reinforcement learning ⋮ Tropical linear algebra with the Łukasiewicz t-norm ⋮ On tropical fractional linear programming ⋮ Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games ⋮ Approximately global optimal control for max-plus linear systems and its application on load distribution ⋮ Tropical Complementarity Problems and Nash Equilibria ⋮ Tropical optimization problems with application to project scheduling with minimum makespan ⋮ On integer images of max-plus linear mappings ⋮ Weak dual residuations applied to tropical linear equations ⋮ Complete solution of tropical vector inequalities using matrix sparsification. ⋮ On two-sided max-linear equations ⋮ A note on tropical linear and integer programs ⋮ Steady states in the scheduling of discrete-time systems ⋮ On \(2 \times 2\) tropical commuting matrices ⋮ On the integer max-linear programming problem ⋮ On Special Cases of the Generalized Max-Plus Eigenproblem ⋮ A multidimensional tropical optimization problem with a non-linear objective function and linear constraints ⋮ A strongly polynomial method for solving integer max-linear optimization problems in a generic case ⋮ Minimizing maximum lateness in two-stage projects by tropical optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The number of extreme points of tropical polyhedra
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• The tropical analogue of polar cones
• Linear and combinatorial optimization in ordered algebraic structures
• Positional strategies for mean payoff games
• The complexity of mean payoff games on graphs
• Duality and separation theorems in idempotent semimodules.
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Tropical convexity
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Introduction to max-linear programming
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• Inferring Min and Max Invariants Using Max-Plus Polyhedra
• Coupling Policy Iteration with Semi-definite Relaxation to Compute Accurate Numerical Invariants in Static Analysis
• Max-linear Systems: Theory and Algorithms
• Precise Relational Invariants Through Strategy Iteration
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• The duality theorem for min-max functions
• Scheduling with AND/OR Precedence Constraints
• -convexity
• A constructive fixed point theorem for min-max functions
• Methods and applications of (max,+) linear algebra
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• The Max-Atom Problem and Its Relevance
• Stochastic Games with Perfect Information and Time Average Payoff
• Verification, Model Checking, and Abstract Interpretation
• Computer Aided Verification
• Static Analysis by Policy Iteration on Relational Domains
• Verification, Model Checking, and Abstract Interpretation
• Idempotent functional analysis: An algebraic approach

This page was built for publication: Tropical linear-fractional programming and parametric mean payoff games