Computing the vertices of tropical polyhedra using directed hypergraphs

Details Computing the vertices of tropical polyhedra using directed hypergraphs Computing the vertices of tropical polyhedra using directed hypergraphs

2009-04-22

arxiv.org/abs/0904.3436v3

Mathematics

Combinatorics

29 pages (A4), 10 figures, 1 table; v2: Improved algorithm in section 5 (using directed hypergraphs), detailed appendix; v3: m

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing the vertices of tropical polyhedra using directed hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the vertices of tropical polyhedra using directed hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the vertices of tropical polyhedra using directed hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275009