The tropical double description method

Xavier Allamigeon 1, 2, 3, * Stéphane Gaubert 4, * Eric Goubault 2
* Auteur correspondant
1 Bureaux des transports
2 LIST - Laboratoire d'Intégration des Systèmes et des Technologies
3 EADS IW - EADS Innovation Works [Suresnes]
4 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 analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
Keywords : convexity in tropical algebra algorithmics and combinatorics of tropical polyhedra computational geometry discrete event systems static analysis
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.47-58, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00455341
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 10:39:37
Dernière modification le : jeudi 10 mai 2018 - 02:05:47
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:52:43

Fichier

AllamigeonGaubertGoubault.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455341, version 1

Collections

CEA | X | INRIA | STACS2010 | PARISTECH | X-CMAP | CMAP | DRT | TDS-MACS | LIST | X-DEP-MATHA

Citation

Xavier Allamigeon, Stéphane Gaubert, Eric Goubault. The tropical double description method. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.47-58, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455341〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

757

Téléchargements de fichiers

149

Contact


archive-ouverte@inria.fr