Minimal half-spaces and external representation of tropical polyhedra

Details Minimal half-spaces and external representation of tropical polyhedra Minimal half-spaces and external representation of tropical polyhedra

2009-08-12

arxiv.org/abs/0908.1586v2

Journal of Algebraic Combinatorics, Volume 33, Number 3, 325-348, 2011

Mathematics

Optimization and Control

19 pages, 4 figures, example added with a new figure, figures improved, references updated

Scientific paper

10.1007/s10801-010-0246-4

We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.

Affiliated with

Also associated with

No associations

Rating

Minimal half-spaces and external representation of tropical polyhedra 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 Minimal half-spaces and external representation of tropical polyhedra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal half-spaces and external representation of tropical polyhedra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-369704