Maximum semidefinite and linear extension complexity of families of polytopes
From MaRDI portal
Publication:1702780
DOI10.1007/s10107-017-1134-7zbMath1384.52008arXiv1605.08538OpenAlexW2964171684MaRDI QIDQ1702780
Stefan Weltge, Volker Kaibel, Gennadiy Averkov
Publication date: 28 February 2018
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.08538
Semidefinite programming (90C22) (n)-dimensional polytopes (52B11) Integer programming (90C10) Linear programming (90C05)
Related Items
A variational principle for ground spaces, On the extension complexity of polytopes separating subsets of the Boolean cube, Strengthening convex relaxations of 0/1-sets using Boolean formulas, Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Convex hulls of curves of genus one
- Extended formulations for polygons
- Smallest compact formulation for the permutahedron
- On the extension complexity of combinatorial polytopes
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Positive semidefinite rank
- Semidefinite representation of convex sets
- Expressing combinatorial optimization problems by linear programs
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Some \(0/1\) polytopes need exponential size extended formulations
- A note on the extension complexity of the knapsack polytope
- Semidefinite Representation of Convex Sets and Convex Hulls
- Extension Complexity of Polytopes with Few Vertices or Facets
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Linear matrix inequality representation of sets
- Disjunctive Programming
- The Matching Polytope has Exponential Extension Complexity
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- Extended formulations in combinatorial optimization
