TY - JOUR

T1 - Maximum semidefinite and linear extension complexity of families of polytopes

AU - Averkov, Gennadiy

AU - Kaibel, Volker

AU - Weltge, Stefan

N1 - Publisher Copyright:
© 2017, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - 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 Brië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(2dd).

AB - 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 Brië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(2dd).

KW - Extension complexity

KW - Polytopes

KW - Semidefinite extended formulations

UR - http://www.scopus.com/inward/record.url?scp=85016184733&partnerID=8YFLogxK

U2 - 10.1007/s10107-017-1134-7

DO - 10.1007/s10107-017-1134-7

M3 - Article

AN - SCOPUS:85016184733

SN - 0025-5610

VL - 167

SP - 381

EP - 394

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -