output
20152021
most citedLog-barrier interior point methods are not strongly polynomial

66 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions
Showing math.OCShow all

7 papers · 1 filter

math.OC2020

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…

math.OC2020

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…

math.OC2018★ 2 cited

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…

math.OC2017★ 66 cited

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…

math.OC2016★ 4 cited

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…

math.OC2016

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…

math.OC2015★ 22 cited

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…