Maximum semidefinite and linear extension complexity of families of polytopes
Maximum semidefinite and linear extension complexity of families of polytopes
复制标题
DOI：
10.1007/s10107-017-1134-7
复制
发表时间：
2018-02-01
影响因子：
2.7
通讯作者：
Weltge, Stefan
中科院分区：
文献类型：
--
作者：
Averkov, Gennadiy;Kaibel, Volker;Weltge, Stefan
我们将多面体族的最大半定线性扩张复杂性与该族的基数及其成员的最小成对豪斯多夫距离联系起来。这个结果直接暗示了0/1-多面体的最大半定扩张复杂性的一个已知下界。我们进一步展示了如何我们的结果可以用来提高相应的边界已知的多边形与整数顶点。我们的几何证明建立在没有别的比一个简单的众所周知的性质最大体积内接椭球凸体。特别地，它不依赖于半定锥上的因式分解，从而避免了根据需要平衡它们的复杂过程，例如，在布里亚
We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known property of maximum volume inscribed ellipsoids of convex bodies. In particular, it does not rely on factorizations over the semidefinite cone and thus avoids involved procedures of balancing them as required, e.g., in BriA