Extended formulations for radial cones

Matthias Walter*, Stefan Weltge

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review


    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 languageEnglish
    Pages (from-to)458-463
    Number of pages6
    JournalOperations research letters
    Issue number5
    Early online date4 Jun 2019
    Publication statusPublished - 1 Sep 2019


    • Extension complexity
    • Matching polytope
    • Odd-cut polyhedron
    • Radial cones

    Fingerprint Dive into the research topics of 'Extended formulations for radial cones'. Together they form a unique fingerprint.

    Cite this