Simple extensions of polytopes
成果类型：
Article
署名作者：
Kaibel, Volker; Walter, Matthias
署名单位：
Otto von Guericke University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-015-0885-2
发表日期：
2015
页码：
381-406
关键词：
摘要：
We introduce the simple extension complexity of a polytope as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto . We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao's on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.