66 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre de Mathématiques Appliquées de l'École polytechniqueFR13 papers
- École PolytechniqueFR12 papers
- Centre National de la Recherche ScientifiqueFR8 papers
- Institut national de recherche en sciences et technologies du numériqueFR6 papers
- Centre Inria de SaclayFR3 papers
- Brigade des Sapeurs Pompiers de ParisFR2 papers
- CERMICSFR2 papers
- École nationale des ponts et chausséesFR2 papers
- Électricité de France (France)FR2 papers
- Indian Statistical Institute, Delhi CentreIN2 papers
- Technische Universität BerlinDE2 papers
- Ashoka UniversityIN1 paper
18 papers
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 Dynamic Programming for Lipschitz Multistage Stochastic Programming
Marianne Akian, Jean-Philippe Chancelier, Benoît Tran
We present an algorithm called Tropical Dynamic Programming (TDP) which builds upper and lower approximations of the Bellman value functions in risk-neutral Multistage Stochastic P…
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…
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…
Intersection multiplicity of a sparse curve and a low-degree curve
Pascal Koiran, Mateusz Skomra
Let be a polynomial of degree and let be a polynomial with monomials. We want to estimate the maximal multiplicit…
Matrix versions of the Hellinger distance
Rajendra Bhatia, Stephane Gaubert, Tanvi Jain
On the space of positive definite matrices we consider distance functions of the form $d(A,B)=\left[\tr\mathcal{A}(A,B)-\tr\mathcal{G}(A,B)\right]^{1/2},$ where …
A stochastic algorithm for deterministic multistage optimization problems
Marianne Akian, Jean-Philippe Chancelier, Benoît Tran
Several attempts to dampen the curse of dimensionnality problem of the Dynamic Programming approach for solving multistage optimization problems have been investigated. One popular…
Nonsmooth Aggregative Games with Coupling Constraints and Infinitely Many Classes of Players
Paulin Jacquot, Cheng Wan
After defining a pure-action profile in a nonatomic aggregative game, where players have specific compact convex pure-action sets and nonsmooth convex cost functions, as a square-i…
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…
Horofunction Compactifications of Symmetric Spaces
Thomas Haettel, Anna-Sofie Schilling, Cormac Walsh +1
We consider horofunction compactifications of symmetric spaces with respect to invariant Finsler metrics. We show that any (generalized) Satake compactification can be realized as…
Tropical compound matrix identities
Marianne Akian, Stephane Gaubert, Adi Niv
We prove identities on compound matrices in extended tropical semirings. Such identities include analogues to properties of conjugate matrices, powers of matrices and~$\adj(A)\det(…
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…
A tropical isoperimetric inequality
Jules Depersin, Stéphane Gaubert, Michael Joswig
We introduce tropical analogues of the notion of volume of polytopes, leading to a tropical version of the (discrete) classical isoperimetric inequality. The planar case is element…
Tropical totally positive matrices
Stéphane Gaubert, Adi Niv
We investigate the tropical analogues of totally positive and totally nonnegative matrices. These arise when considering the images by the nonarchimedean valuation of the correspon…
An Accretive Operator Approach to Ergodic Problems for Zero-Sum Games
Antoine Hochart
Mean payoff stochastic games can be studied by means of a nonlinear spectral problem involving the Shapley operator: the ergodic equation. A solution consists in a scalar, called t…
Non-archimedean valuations of eigenvalues of matrix polynomials
Marianne Akian, Ravindra Bapat, Stéphane Gaubert
We establish general weak majorization inequalities, relating the leading exponents of the eigenvalues of matrices or matrix polynomials over the field of Puiseux series with the t…
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…