The tropical double description method

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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455341
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:39:37 AM
Last modification on : Wednesday, March 27, 2019 - 4:08:29 PM
Long-term archiving on : 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. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.47-58. ⟨inria-00455341⟩

Share

Metrics

Record views

944

Files downloads

188