Extended formulations for radial cones

Matthias Walter, Stefan Weltge

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

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.

OriginalspracheEnglisch
Seiten (von - bis)458-463
Seitenumfang6
FachzeitschriftOperations Research Letters
Jahrgang47
Ausgabenummer5
DOIs
PublikationsstatusVeröffentlicht - Sept. 2019

Fingerprint

Untersuchen Sie die Forschungsthemen von „Extended formulations for radial cones“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren