66 citations · 468 across the 34 of their papers we have counts for
39 papers
Sharper bounds on the thresholds for sensitive and Blackwell optimality
Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément +1
In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount o…
Computing the Congestion Phases of Dynamical Systems with Priorities and Application to Emergency Departments
Xavier Allamigeon, Pascal Capetillo, Stéphane Gaubert
Medical emergency departments are complex systems in which patients must be treated according to priority rules based on the severity of their condition. We develop a model of emer…
Stationary regimes of piecewise linear dynamical systems with priorities
Xavier Allamigeon, Pascal Capetillo, Stephane Gaubert
Dynamical systems governed by priority rules appear in the modeling of emergency organizations and road traffic. These systems can be modeled by piecewise linear time-delay dynamic…
Signed tropicalization of polar cones
Marianne Akian, Xavier Allamigeon, Stéphane Gaubert +1
We study the tropical analogue of the notion of polar of a cone, working over the semiring of tropical numbers with signs. We characterize the cones which arise as polars of sets o…
Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on a…
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho +2
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an -variable linear program in standard form, the iteration…
Computing Transience Bounds of Emergency Call Centers: a Hierarchical Timed Petri Net Approach
Xavier Allamigeon, Marin Boyet, Stephane Gaubert
A fundamental issue in the analysis of emergency call centers is to estimate the time needed to return to a congestion-free regime after an unusual event with a massive arrival of…
No self-concordant barrier interior point method is strongly polynomial
Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame
It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the…
Formalizing the Face Lattice of Polyhedra
Xavier Allamigeon, Ricardo D. Katz, Pierre-Yves Strub
Faces play a central role in the combinatorial and computational aspects of polyhedra. In this paper, we present the first formalization of faces of polyhedra in the proof assistan…
Tropical complementarity problems and Nash equilibria
Xavier Allamigeon, Stéphane Gaubert, Frédéric Meunier
Linear complementarity programming is a generalization of linear programming which encompasses the computation of Nash equilibria for bimatrix games. While the latter problem is PP…
The tropicalization of the entropic barrier
Xavier Allamigeon, Abdellah Aznag, Stéphane Gaubert +1
The entropic barrier, studied by Bubeck and Eldan (Proc. Mach. Learn. Research, 2015), is a self-concordant barrier with asymptotically optimal self-concordance parameter. In this…
A convex programming approach to solve posynomial systems
Marianne Akian, Xavier Allamigeon, Marin Boyet +1
We exhibit a class of classical or tropical posynomial systems which can be solved by reduction to linear or convex programming problems. This relies on a notion of colorful vector…
Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area
Stéphane Gaubert, Marianne Akian, Xavier Allamigeon +16
We portray the evolution of the Covid-19 epidemic during the crisis of March-April 2020 in the Paris area, by analyzing the medical emergency calls received by the EMS of the four…
Piecewise Affine Dynamical Models of Timed Petri Nets -- Application to Emergency Call Centers
Xavier Allamigeon, Marin Boyet, Stéphane Gaubert
We study timed Petri nets, with preselection and priority routing. We represent the behavior of these systems by piecewise affine dynamical systems. We use tools from the theory of…
Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
Semidefinite programming can be considered over any real closed field, including fields of Puiseux series equipped with their nonarchimedean valuation. Nonarchimedean semidefinite…
The tropical analogue of the Helton-Nie conjecture is true
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
Helton and Nie conjectured that every convex semialgebraic set over the field of real numbers can be written as the projection of a spectrahedron. Recently, Scheiderer disproved th…
Log-barrier interior point methods are not strongly polynomial
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with inequalities in dimension for…
A formalization of convex polyhedra based on the simplex method
Xavier Allamigeon, Ricardo D. Katz
We present a formalization of convex polyhedra in the proof assistant Coq. The cornerstone of our work is a complete implementation of the simplex method, together with the proof o…
Maximal lower bounds in the Löwner order
Nikolas Stott
We show that the set of maximal lower bounds of two symmetric matrices with respect to the Löwner order can be identified to the quotient set . Here, $(p,…
Stationary solutions of discrete and continuous Petri nets with priorities
Xavier Allamigeon, Vianney Boeuf, Stéphane Gaubert
We study a continuous dynamics for a class of Petri nets which allows the routing at non-free choice places to be determined by priorities rules. We show that this dynamics can be…
Tropical spectrahedra
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
We introduce tropical spectrahedra, defined as the images by the nonarchimedean valuation of spectrahedra over the field of real Puiseux series. We provide an explicit polyhedral c…
Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
A general issue in computational optimization is to develop combinatorial algorithms for semidefinite programming. We address this issue when the base field is nonarchimedean. We p…
Performance evaluation of an emergency call center: tropical polynomial systems applied to timed Petri nets
Xavier Allamigeon, Vianney Bœuf, Stéphane Gaubert
We analyze a timed Petri net model of an emergency call center which processes calls with different levels of priority. The counter variables of the Petri net represent the cumulat…
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…