66 citations · 468 across the 34 of their papers we have counts for
5 papers · 1 filter
Tropicalization of facets of polytopes
Xavier Allamigeon, Ricardo D. Katz
It is known that any tropical polytope is the image under the valuation map of ordinary polytopes over the Puiseux series field. The latter polytopes are called lifts of the tropic…
The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert
We introduce an algorithm which solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a flip invariance property on the set of ac…
Long and winding central paths
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We disprove a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with inequalities in dimensio…
Formal Proofs for Nonlinear Optimization
Victor Magron, Xavier Allamigeon, Stéphane Gaubert +1
We present a formally verified global optimization framework. Given a semialgebraic or transcendental function and a compact semialgebraic domain , we use the nonlinear maxp…
Certification of Real Inequalities -- Templates and Sums of Squares
Xavier Allamigeon, Stéphane Gaubert, Victor Magron +1
We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. The functions we are dealing with are nonlinear and involve semialgebraic…