arXiv:1308.0454 Abstract | arXiv Analytics

arXiv:1308.0454 [math.CO]Abstract References Reviews Resources

Tropicalizing the simplex algorithm

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig

Published 2013-08-02, updated 2014-12-21Version 2

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.

Comments: v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms

Categories: math.CO, math.OC

Subjects: 14T50, 90C05

Keywords: simplex algorithm, tropicalizing, combinatorial algorithm, tropical analog

Related articles: Most relevant | Search more

arXiv:math/0309351 [math.CO] (Published 2003-09-22, updated 2004-08-20)

The Simplex Algorithm in Dimension Three

Volker Kaibel, Rafael Mechtel, Micha Sharir, Guenter M. Ziegler

arXiv:2004.10443 [math.CO] (Published 2020-04-22)

A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices

Hiroshi Hirai, Yuni Iwamasa

arXiv:math/0301076 [math.CO] (Published 2003-01-09)