Article ID Journal Published Year Pages File Type
1142367 Operations Research Letters 2015 4 Pages PDF
Abstract
Some widely known compact extended formulations have the property that each vertex of the corresponding extension polytope is projected onto a vertex of the target polytope. In this paper, we prove that for heptagons with vertices in general position none of the minimum size extensions has this property. Additionally, for any d≥2 we construct a family of d-polytopes such that at least 19 of all vertices of any of their minimum size extensions is not projected onto vertices.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,