Maximum semidefinite and linear extension complexity of families of polytopes

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Kaibel, Volker; Weltge, Stefan
• 署名单位: Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1134-7
• 发表日期: 2018
• 页码: 381-394
• 关键词: convex-sets; Combinatorial Optimization; REPRESENTATION; hulls

摘要

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 << t et al. (Math Program 153(1):179-199, 2015). Moreover, we show that the linear extension complexity of every d-dimensional 0/1-polytope is bounded from above by O(2(d)/d).