Maximum semidefinite and linear extension complexity of families of polytopes

作者：Averkov Gennadiy; Kaibel Volker; Weltge Stefan^*

来源：Mathematical Programming, 2018, 167(2): 381-394.

DOI：10.1007/s10107-017-1134-7

• Semidefinite extended formulations
• Extension complexity
• Polytopes

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).

• 出版日期2018-2