66 citations · 468 across the 34 of their papers we have counts for
5 papers · 1 filter
Combinatorial simplex algorithms can solve mean payoff games
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on combinatorial data only. We show that any algorithm of this kind admits a tr…
Tropical Fourier-Motzkin elimination, with an application to real-time verification
Xavier Allamigeon, Uli Fahrenberg, Stéphane Gaubert +2
We introduce a generalization of tropical polyhedra able to express both strict and non-strict inequalities. Such inequalities are handled by means of a semiring of germs (encoding…
Tropicalizing the simplex algorithm
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We develop a tropical analog of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including th…
Certification of inequalities involving transcendental functions: combining SDP and max-plus approximation
Xavier Allamigeon, Stéphane Gaubert, Victor Magron +1
We consider the problem of certifying an inequality of the form , , where is a multivariate transcendental function, and is a compact semialgebr…
Certification of Bounds of Non-linear Functions: the Templates Method
Xavier Allamigeon, Stéphane Gaubert, Victor Magron +1
The aim of this work is to certify lower bounds for real-valued multivariate functions, defined by semialgebraic or transcendental expressions. The certificate must be, eventually,…