Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142367 | Operations Research Letters | 2015 | 4 Pages |
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
Kanstantsin Pashkovich, Stefan Weltge,