Tropicalizing the simplex algorithm

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 : mercredi 14 novembre 2018 - 15:20:11

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

414