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

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