Computing the Vertices of Tropical Polyhedra using Directed Hypergraphs

Xavier Allamigeon 1, 2 Stéphane Gaubert 1, 2 Eric Goubault 3, 4
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 establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if, a directed hypergraph, constructed from the subdifferentials of the active constraints at this point, admits a unique strongly connected component that is maximal with respect to the reachability relation (all the other strongly connected components have access to it). This property can be checked in almost linear-time. This allows us to develop a tropical analogue of the classical double description method, which computes a minimal internal representation (in terms of vertices) of a polyhedron defined externally (by half-spaces or hyperplanes). We provide theoretical worst case complexity bounds and report extensive experimental tests performed using the library TPLib, showing that this method outperforms the other existing approaches.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2013, 49, pp.247-279. 〈10.1007/s00454-012-9469-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00782862
Contributeur : Canimogy Cogoulane <>
Soumis le : mercredi 30 janvier 2013 - 17:06:54
Dernière modification le : jeudi 10 mai 2018 - 02:05:44

Lien texte intégral

Identifiants

Collections

Citation

Xavier Allamigeon, Stéphane Gaubert, Eric Goubault. Computing the Vertices of Tropical Polyhedra using Directed Hypergraphs. Discrete and Computational Geometry, Springer Verlag, 2013, 49, pp.247-279. 〈10.1007/s00454-012-9469-6〉. 〈hal-00782862〉

Partager

Métriques

Consultations de la notice

554