Extension complexity of low-dimensional polytopes
Extension complexity of low-dimensional polytopes
复制标题
低维多胞形的可拓复杂度
DOI：
10.1090/tran/8614
复制
发表时间：
2022
影响因子：
1.3
通讯作者：
Zhao, Yufei
中科院分区：
文献类型：
--
作者：
Kwan, Matthew;Sauermann, Lisa;Zhao, Yufei
有时，可以将复杂的多面体表示为简单得多的多面体的投影。为了量化这一现象，将多面体的扩张复杂性定义为多面体(可能是高维的)多面体的最小面数，由此可以得到一个(线性)投影。这一概念的动机是它与组合优化的相关性，并已被深入研究与重要的优化问题相关的各种特定的多面体。在本文中，我们将可拓复杂性作为一般多面体的一个参数来研究，更具体地说，考虑了各种低维多面体。
Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytopeis defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from whichcan be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes.
登录
查看更多内容
DOI：
10.1007/bf00535300
发表时间：
1963
期刊：
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
影响因子：
--
作者：
A. Rényi;R. Sulanke
通讯作者：
A. Rényi;R. Sulanke
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
R. Gelca;T. Andreescu
通讯作者：
T. Andreescu
通信复杂性、线性优化和矩阵非负秩的下界
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
LeRoy Beasely;Troy Lee;H. Klauck;Dirk Oliver;Theis
通讯作者：
Theis
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
M. Reitzner
通讯作者：
M. Reitzner
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
E. Spodarev
通讯作者：
E. Spodarev