66 citations · 154 across the 8 of their papers we have counts for
Showing math.COShow all
2 papers · 1 filter
math.CO2013★ 17 cited
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…
math.CO2013★ 56 cited
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…