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, X - École polytechnique, 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 10 mai 2018 - 02:04:06

Lien texte intégral

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

407