Tropicalizing the simplex algorithm

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stéphane Gaubert 1, 2 Michael Joswig 3
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (2), 〈10.1137/130936464〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00930913
Contributeur : Pascal Benchimol <>
Soumis le : mardi 14 janvier 2014 - 16:28:55
Dernière modification le : jeudi 11 janvier 2018 - 06:22:33

Identifiants

Citation

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Tropicalizing the simplex algorithm. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (2), 〈10.1137/130936464〉. 〈hal-00930913〉

Partager

Métriques

Consultations de la notice

330