The tropical double description method

Xavier Allamigeon 1, 2, 3, * Stéphane Gaubert 4, * Eric Goubault 2
* Corresponding author
4 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 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.
Document type :
Conference papers
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


https://hal.inria.fr/inria-00455341
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:39:37 AM
Last modification on : Thursday, February 9, 2017 - 3:14:42 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:52:43 PM

File

AllamigeonGaubertGoubault.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455341, version 1

Collections

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>

Share

Metrics

Record views

458

Document downloads

103