66 citations · 468 across the 34 of their papers we have counts for
4 papers · 1 filter
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…