On the extension complexity of combinatorial polytopes
From MaRDI portal
Publication:745682
DOI10.1007/978-3-642-39206-1_6zbMATH Open1336.90095arXiv1302.2340OpenAlexW1942134738MaRDI QIDQ745682FDOQ745682
Authors: David Avis, Hans Raj Tiwary 
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B, Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1302.2340
Recommendations
- On the extension complexity of combinatorial polytopes
- Extension complexity of low-dimensional polytopes
- On the extension complexity of polytopes separating subsets of the Boolean cube
- Extension complexity of independent set polytopes
- On the combinatorial complexity of approximating polytopes
- On the combinatorial complexity of approximating polytopes
- On the expansion of combinatorial polytopes
- Extension complexity of polytopes with few vertices or facets
- On the linear extension complexity of regular \(n\)-gons
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Introduction to algorithms.
- Title not available (Why is that?)
- Reducibility among Combinatorial Problems
- Lectures on Polytopes
- Expressing combinatorial optimization problems by linear programs
- Linear vs. semidefinite extended formulations
- Geometry of cuts and metrics
- Some simplified NP-complete graph problems
- The max-cut problem on graphs not contractible to \(K_ 5\)
- On the distributional complexity of disjointness
- A note on the extension complexity of the knapsack polytope
- Nondeterministic Quantum Query and Communication Complexities
- Generating facets for the cut polytope of a graph by triangular elimination
- Two-party Bell inequalities derived from combinatorics via triangular elimination
Cited In (30)
- A note on the extension complexity of the knapsack polytope
- The Matching Polytope has Exponential Extension Complexity
- Exponential lower bounds for polytopes in combinatorial optimization
- Extension Complexity of Independent Set Polytopes
- Generalized probabilistic theories and conic extensions of polytopes
- Maximum semidefinite and linear extension complexity of families of polytopes
- On permuting some coordinates of polytopes
- Some complete and intermediate polynomials in algebraic complexity theory
- A generalization of extension complexity that captures P
- On the extension complexity of scheduling polytopes
- Common information and unique disjointness
- Title not available (Why is that?)
- Lower bounds on the sizes of integer programs without additional variables
- Simple extensions of polytopes
- On polyhedral extension of some LP theorems
- Parameterized extension complexity of independent set and related problems
- Average case polyhedral complexity of the maximum stable set problem
- The last dozen of years of or research in Czechia and Slovakia
- Pitch, extension complexity, and covering problems
- Extension complexity of formal languages
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Extended formulations for radial cones
- On the extension complexity of combinatorial polytopes
- New limits of treewidth-based tractability in optimization
- Extension complexity of stable set polytopes of bipartite graphs
- \(N\)-extendible posets, and how to minimize total weighted completion time
- On the extension complexity of polytopes separating subsets of the Boolean cube
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
- Polynomial size linear programs for problems in \textsc{P}
- Extended formulations for convex hulls of some bilinear functions
This page was built for publication: On the extension complexity of combinatorial polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745682)
