On the extension complexity of combinatorial polytopes
成果类型：
Article
署名作者：
Avis, David; Tiwary, Hans Raj
署名单位：
McGill University; Universite de Montreal; McGill University; Kyoto University; Universite Libre de Bruxelles
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-014-0764-2
发表日期：
2015
页码：
95-115
关键词：
摘要：
In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.