Tropical linear-fractional programming and parametric mean payoff games
Tropical linear-fractional programming and parametric mean payoff games
复制标题
DOI：
10.1016/j.jsc.2011.12.049
复制
发表时间：
2011-01
期刊：
影响因子：
--
通讯作者：
S. Gaubert;Ricardo D. Katz;Sergeĭ Sergeev
中科院分区：
文献类型：
--
作者：
S. Gaubert;Ricardo D. Katz;Sergeĭ Sergeev
热带多面体最近被用来表示静态分析中的析取不变量。为了处理更大的实例，需要开发经典线性规划结果的热带模拟。这一动机引导我们研究经典线性分式规划问题的热带模拟。我们构造了一个相关的参数平均收益博弈问题，并证明了给定点的最优性，或问题的无界性，可以通过展示具有我们组合表征的某些无穷小属性（涉及博弈的值及其导数）的一个参与者的策略来证明。我们使用这个想法来设计一个类似牛顿的算法来解决热带线性分数规划问题，通过简化为一系列辅助平均收益博弈问题。
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.