The matching problem has no small symmetric SDP (Q1675264): Difference between revisions

@@ Property / cites work @@
+No Small Linear Program Approximates Vertex Cover Within a Factor 2 − <i>ɛ</i>
+Normal rank
@@ Property / cites work @@
+An Algebraic Approach to Symmetric Extended Formulations
+Normal rank
@@ Property / cites work @@
+The matching polytope does not admit fully-polynomial size relaxation schemes
+Normal rank
@@ Property / cites work @@
+The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes
+Normal rank
@@ Property / cites work @@
+Approximation Limits of Linear Programs (Beyond Hierarchies)
+Normal rank
@@ Property / cites work @@
+Inapproximability of Combinatorial Problems via Small LPs and SDPs
+Normal rank
@@ Property / cites work @@
+An information complexity approach to extended formulations
+Normal rank
@@ Property / cites work @@
+On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
+Normal rank
@@ Property / cites work @@
+On the existence of 0/1 polytopes with high semidefinite extension complexity
+Normal rank
@@ Property / cites work @@
+Approximate Constraint Satisfaction Requires Large LP Relaxations
+Normal rank
@@ Property / cites work @@
+Q4882944
@@ Property / cites work: Q4882944 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum matching and a polyhedron with 0,1-vertices
+Normal rank
@@ Property / cites work @@
+Linear vs. semidefinite extended formulations
@@ Property / cites work: Linear vs. semidefinite extended formulations / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential Lower Bounds for Polytopes in Combinatorial Optimization
+Normal rank
@@ Property / cites work @@
+Smallest compact formulation for the permutahedron
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Lifts of Convex Sets and Cone Factorizations
@@ Property / cites work: Lifts of Convex Sets and Cone Factorizations / rank @@
+Normal rank
@@ Property / cites work @@
+Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
+Normal rank
@@ Property / cites work @@
+Symmetry Matters for the Sizes of Extended Formulations
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Semidefinite Programming
@@ Property / cites work: Semidefinite Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank