Hidden vertices in extensions of polytopes

Kanstantsin Pashkovich; Stefan Weltge

doi:10.1016/j.orl.2015.01.004

Hidden vertices in extensions of polytopes

Kanstantsin Pashkovich, Stefan Weltge

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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 d2 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.

Original language	English
Pages (from-to)	161-164
Number of pages	4
Journal	Operations Research Letters
Volume	43
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2015.01.004
State	Published - Mar 2015
Externally published	Yes

Keywords

Additional vertex
Extended formulation
Minimal extension
Polytope
Projection

Access to Document

10.1016/j.orl.2015.01.004

Cite this

@article{223c9aa0f40d460ea18c8c61daec26ad,

title = "Hidden vertices in extensions of polytopes",

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 d2 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.",

keywords = "Additional vertex, Extended formulation, Minimal extension, Polytope, Projection",

author = "Kanstantsin Pashkovich and Stefan Weltge",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = mar,

doi = "10.1016/j.orl.2015.01.004",

language = "English",

volume = "43",

pages = "161--164",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Hidden vertices in extensions of polytopes

AU - Pashkovich, Kanstantsin

AU - Weltge, Stefan

PY - 2015/3

Y1 - 2015/3

N2 - 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 d2 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.

AB - 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 d2 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.

KW - Additional vertex

KW - Extended formulation

KW - Minimal extension

KW - Polytope

KW - Projection

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

U2 - 10.1016/j.orl.2015.01.004

DO - 10.1016/j.orl.2015.01.004

M3 - Article

AN - SCOPUS:84961290078

SN - 0167-6377

VL - 43

SP - 161

EP - 164

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Hidden vertices in extensions of polytopes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this