On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity

DOI10.1007/978-3-642-40450-4_19zbMath1395.90241OpenAlexW2477453038MaRDI QIDQ2849312

Jop Briët, Sebastian Pokutta, Daniel Dadush

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/24053

zbMATH Keywords

extended formulationsextension complexitysemidefinite extended formulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (7)

The matching problem has no small symmetric SDP ⋮ Four-dimensional polytopes of minimum positive semidefinite rank ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Positive semidefinite rank ⋮ Worst-case results for positive semidefinite rank ⋮ Semidefinite Descriptions of the Convex Hull of Rotation Matrices ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity