Extended formulations for radial cones

Matthias Walter; Stefan Weltge

doi:10.1016/j.orl.2019.05.004

Extended formulations for radial cones

Matthias Walter, Stefan Weltge

Associate Professorship of Discrete Mathematics

University of Twente

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

Abstract

This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.

Original language	English
Pages (from-to)	458-463
Number of pages	6
Journal	Operations Research Letters
Volume	47
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2019.05.004
State	Published - Sep 2019

Keywords

Extension complexity
Matching polytope
Odd-cut polyhedron
Radial cones

Access to Document

10.1016/j.orl.2019.05.004

Cite this

@article{a83f5c0b6fb44d788fc1f820d9312d55,

title = "Extended formulations for radial cones",

abstract = "This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvo{\ss} 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.",

keywords = "Extension complexity, Matching polytope, Odd-cut polyhedron, Radial cones",

author = "Matthias Walter and Stefan Weltge",

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

year = "2019",

month = sep,

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

language = "English",

volume = "47",

pages = "458--463",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Extended formulations for radial cones

AU - Walter, Matthias

AU - Weltge, Stefan

PY - 2019/9

Y1 - 2019/9

N2 - This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.

AB - This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.

KW - Extension complexity

KW - Matching polytope

KW - Odd-cut polyhedron

KW - Radial cones

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

U2 - 10.1016/j.orl.2019.05.004

DO - 10.1016/j.orl.2019.05.004

M3 - Article

AN - SCOPUS:85067260510

SN - 0167-6377

VL - 47

SP - 458

EP - 463

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Extended formulations for radial cones

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this