Extension complexities of Cartesian products involving a pyramid

Hans Raj Tiwary; Stefan Weltge; Rico Zenklusen

doi:10.1016/j.ipl.2017.07.011

Extension complexities of Cartesian products involving a pyramid

Hans Raj Tiwary, Stefan Weltge, Rico Zenklusen

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

Abstract

It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P,Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.

Original language	English
Pages (from-to)	11-13
Number of pages	3
Journal	Information Processing Letters
Volume	128
DOIs	https://doi.org/10.1016/j.ipl.2017.07.011
State	Published - Dec 2017
Externally published	Yes

Keywords

Cartesian product
Computational geometry
Extended formulations

Access to Document

10.1016/j.ipl.2017.07.011

Cite this

@article{649f659f014a4f1eb5689602f6ad8481,

title = "Extension complexities of Cartesian products involving a pyramid",

abstract = "It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P,Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.",

keywords = "Cartesian product, Computational geometry, Extended formulations",

author = "Tiwary, {Hans Raj} and Stefan Weltge and Rico Zenklusen",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = dec,

doi = "10.1016/j.ipl.2017.07.011",

language = "English",

volume = "128",

pages = "11--13",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Extension complexities of Cartesian products involving a pyramid

AU - Tiwary, Hans Raj

AU - Weltge, Stefan

AU - Zenklusen, Rico

PY - 2017/12

Y1 - 2017/12

N2 - It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P,Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.

AB - It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P,Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.

KW - Cartesian product

KW - Computational geometry

KW - Extended formulations

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

U2 - 10.1016/j.ipl.2017.07.011

DO - 10.1016/j.ipl.2017.07.011

M3 - Article

AN - SCOPUS:85025665609

SN - 0020-0190

VL - 128

SP - 11

EP - 13

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Extension complexities of Cartesian products involving a pyramid

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this