%0 Journal Article
%T Tropicalizing the simplex algorithm
%A Xavier Allamigeon
%A Pascal Benchimol
%A St¨¦phane Gaubert
%A Michael Joswig
%J Mathematics
%D 2013
%I arXiv
%R 10.1137/130936464
%X 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 the computation of reduced costs, in O(n(m+n)) time, where m is the number of constraints and n is the dimension.
%U http://arxiv.org/abs/1308.0454v2