A geometric lower bound on the extension complexity of polytopes based on the f-vector
(2021) Discrete Applied Mathematics — Vol. 303, p. 22-38 (2021)
Files
CORE_RP_3172.pdf
Open Access - Adobe PDF
- 854.93 KB
Details
- Authors
- Abstract
- A linear extension of a polytope is any polytope which can be mapped onto via an affine transformation. The extension complexity of a polytope is the minimum number of facets of any linear extension of this polytope. In general, computing the extension complexity of a given polytope is difficult. The extension complexity is also equal to the nonnegative rank of any slack matrix of the polytope. In this paper, we introduce a new geometric lower bound on the extension complexity of a polytope, i.e., which relies only on the knowledge of some of its geometric characteristics. It is based on the monotone behaviour of the -vector of polytopes under affine maps. We present numerical results showing that this bound can improve upon existing geometric lower bounds, and provide a generalization of this lower bound for the nonnegative rank of any matrix.
- Affiliations
Citations
Dewez, J., Gillis, N., & Glineur, F. (2021). A geometric lower bound on the extension complexity of polytopes based on the f-vector. Discrete Applied Mathematics, 303, 22-38. https://doi.org/10.1016/j.dam.2020.09.028 (Original work published 2021)