Publications (8)
A Privacy-preserving Disaggregation Algorithm for Non-intrusive Management of Flexible Energy
Paulin Jacquot, Olivier Beaude, Pascal Benchimol +2
We consider a resource allocation problem involving a large number of agents with individual constraints subject to privacy, and a central operator whose objective is to optimizing…
Tropicalizing the simplex algorithm
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We develop a tropical analog of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including 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 Privacy-preserving Method to Optimize Distributed Resource Allocation
Olivier Beaude, Pascal Benchimol, Stéphane Gaubert +2
We consider a resource allocation problem involving a large number of agents with individual constraints subject to privacy, and a central operator whose objective is to optimize a…
Combinatorial simplex algorithms can solve mean payoff games
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on combinatorial data only. We show that any algorithm of this kind admits a tr…
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…
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…
Resource constrained shortest path algorithm for EDF short-term thermal production planning problem
Markus Kruber, Axel Parmentier, Pascal Benchimol
Unit commitment problem on an electricity network consists in choosing the production plan of the plants (units) of a company in order to meet demand constraints. It is generally s…