Simple extensions of polytopes
Simple extensions of polytopes
复制标题
多面体的简单扩展
DOI：
10.1007/s10107-015-0885-2
复制
发表时间：
2015
影响因子：
2.7
通讯作者：
Matthias Walter
中科院分区：
文献类型：
--
作者：
Volker Kaibel;Matthias Walter
我们引入了多边形的简单扩展复杂度，即任何可以被投影到的简单（即线性规划意义上的非退化）多边形的最小面数。我们设计了一种组合方法来建立简单扩展复杂度的下界，并证明了几种多面体具有较大的简单扩展复杂度。这些例子包括完全图的生成树和完美匹配多面体、非平凡可分解有向无环图的无约束流多面体、超简单体以及顶点数在一定范围内的随机0/1多面体。在得到完美匹配多面体的结果的过程中，我们推广了Padberg和Rao关于这些多面体邻接结构的结果。除了在材料的扩展抽象(凯贝尔和沃尔特在整数规划和组合优化。计算机科学课堂讲稿，卷8494。施普林格，柏林，2014)我们包括省略的证明，支持数字和已知上限技术的分析。
We introduce thesimple extension complexityof a polytopeas 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.
登录
查看更多内容
DOI：
10.1016/j.orl.2007.09.003
发表时间：
2008-05
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
D. Bienstock
通讯作者：
D. Bienstock
DOI：
10.1090/dimacs/001
发表时间：
1996-03
期刊：
--
影响因子：
--
作者：
A. Schrijver
通讯作者：
A. Schrijver
关于背包多面体可拓复杂度的一个注记
影响因子：
1.1
作者：
S. Pokutta;M. Vyve
通讯作者：
M. Vyve
影响因子：
1.7
作者：
G. Gallo;C. Sodini
通讯作者：
C. Sodini
全面体对称扩展尺寸的严格下界及类似结果
影响因子：
1.7
作者：
Kanstantsin Pashkovich
通讯作者：
Kanstantsin Pashkovich