Sergei Sergeev
Research Subjects
Sergei Sergeev has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Ricardo David Katz
CONICET, Instituto de Matemática “Beppo Levi”, Universidad Nacional de Rosario, Avenida Pellegrini 250, 2000 Rosario, Argentina
1 shared publication - Stéphane Gaubert
INRIA and CMAP École polytechnique Palaiseau France
1 shared publication
Latest Publications
- Open Access
Tropical linear-fractional programming and parametric mean payoff games
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.
Open AccessTropical linear-fractional programming and parametric mean payoff games
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.
- Open Access
On the problem Ax=λBx in max algebra: every system of intervals is a spectrum
We consider the two-sided eigenproblem Ax=\lambda Bx over max algebra. It is shown that any finite system of real intervals and points can be represented as spectrum of this eigenproblem.
Open AccessOn the problem Ax=λBx in max algebra: every system of intervals is a spectrum
We consider the two-sided eigenproblem Ax=\lambda Bx over max algebra. It is shown that any finite system of real intervals and points can be represented as spectrum of this eigenproblem.