Extended formulations for radial cones

Matthias Walter, Stefan Weltge

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

Fingerprint

Extended Formulations
Polyhedron
Cones
Cone
Polynomials
Perfect Matching
Polarity
Polytope
Odd
Polynomial
Vertex of a graph

Keywords

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

Cite this

Walter, Matthias ; Weltge, Stefan. / Extended formulations for radial cones. In: Operations research letters. 2019 ; Vol. 47, No. 5. pp. 458-463.
@article{a8dba831d3ba42eb844277e540aaf4af,
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",
year = "2019",
month = "9",
day = "1",
doi = "10.1016/j.orl.2019.05.004",
language = "English",
volume = "47",
pages = "458--463",
journal = "Operations research letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "5",

}

Extended formulations for radial cones. / Walter, Matthias; Weltge, Stefan.

In: Operations research letters, Vol. 47, No. 5, 01.09.2019, p. 458-463.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Extended formulations for radial cones

AU - Walter, Matthias

AU - Weltge, Stefan

PY - 2019/9/1

Y1 - 2019/9/1

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

VL - 47

SP - 458

EP - 463

JO - Operations research letters

JF - Operations research letters

SN - 0167-6377

IS - 5

ER -