Tropicalizing the simplex algorithm
| Autor: | Allamigeon, Xavier, Benchimol, Pascal, Gaubert, Stéphane, Joswig, Michael |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | SIAM J. Discrete Math. 29:2 (2015) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1137/130936464 |
| Popis: | 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. Comment: v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms |
| Databáze: | arXiv |
| Externí odkaz: |
|