Extension complexity of the correlation polytope

Pierre Aboulker; Samuel Fiorini; Tony Huynh; Marco Macchia; Johanna Seif

doi:10.1016/j.orl.2018.12.001

Extension complexity of the correlation polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh, Marco Macchia, Johanna Seif

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

2 Citations (Scopus)

Abstract

We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2^{O(tw(G)+logn)}, where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.

Original language	English
Pages (from-to)	47-51
Number of pages	5
Journal	Operations Research Letters
Volume	47
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2018.12.001
Publication status	Published - 1 Jan 2019
Externally published	Yes

Keywords

Correlation polytope
Extension complexity
Graph minors
Machine learning
Treewidth

Access to Document

10.1016/j.orl.2018.12.001

Cite this

@article{5160cb99b8be40559c1e95d7ab9e4bc8,

title = "Extension complexity of the correlation polytope",

abstract = "We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.",

keywords = "Correlation polytope, Extension complexity, Graph minors, Machine learning, Treewidth",

author = "Pierre Aboulker and Samuel Fiorini and Tony Huynh and Marco Macchia and Johanna Seif",

year = "2019",

month = jan,

day = "1",

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

language = "English",

volume = "47",

pages = "47--51",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Extension complexity of the correlation polytope

AU - Aboulker, Pierre

AU - Fiorini, Samuel

AU - Huynh, Tony

AU - Macchia, Marco

AU - Seif, Johanna

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.

AB - We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.

KW - Correlation polytope

KW - Extension complexity

KW - Graph minors

KW - Machine learning

KW - Treewidth

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

U2 - 10.1016/j.orl.2018.12.001

DO - 10.1016/j.orl.2018.12.001

M3 - Article

AN - SCOPUS:85059153137

SN - 0167-6377

VL - 47

SP - 47

EP - 51

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Extension complexity of the correlation polytope

Abstract

Keywords

Access to Document

Other files and links

Cite this