Maximum semidefinite and linear extension complexity of families of polytopes
OPEN ACCESS
Loading...
Author / Creator
Date
2017-02
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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).
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
167 (2)
Pages / Article No.
381 - 394
Publisher
Springer
Event
Edition / version
Methods
Geographic location
Date collected
Date created
Subject
Semidefinite extended formulations; Extension complexity; Polytopes
Organisational unit
03873 - Weismantel, Robert / Weismantel, Robert
Notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.