期刊论文详细信息
JOURNAL OF COMBINATORIAL THEORY SERIES A 卷:120
Minimal external representations of tropical polyhedra
Article
Allamigeon, Xavier1,2  Katz, Ricardo D.3 
[1] Ecole Polytech, INRIA, F-91128 Palaiseau, France
[2] Ecole Polytech, CMAP, F-91128 Palaiseau, France
[3] Univ Nacl Rosario, CONICET, Inst Matemat Beppo Levi, RA-2000 Rosario, Santa Fe, Argentina
关键词: Tropical convexity;    Max-plus convexity;    Polyhedra;    Polytopes;    Supporting half-spaces;    External representations;    Cell complexes;   
DOI  :  10.1016/j.jcta.2013.01.011
来源: Elsevier
PDF
【 摘 要 】

Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of their polar cones provide external representations containing in general superfluous half-spaces. In this paper, we prove that any tropical polyhedral cone in R-n (also known as tropical polytope in the literature) admits an essentially unique minimal external representation. The result is obtained by establishing a (partial) anti-exchange property of half-spaces. Moreover, we show that the apices of the half-spaces appearing in such non-redundant external representations are vertices of the cell complex associated with the polyhedral cone. We also establish a necessary condition for a vertex of this cell complex to be the apex of a non-redundant half-space. It is shown that this condition is sufficient for a dense class of polyhedral cones having generic extremities. (c) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free   

【 预 览 】
附件列表
Files Size Format View
10_1016_j_jcta_2013_01_011.pdf 1064KB PDF download
  文献评价指标  
  下载次数:1次 浏览次数:0次