Extended formulations for radial cones

Matthias Walter*, Stefan Weltge

*Corresponding author for this work

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

    Keywords

    • 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