Average case polyhedral complexity of the maximum stable set problem (Q344955): Difference between revisions

@@ Property / cites work @@
+On the extension complexity of combinatorial polytopes
+Normal rank
@@ Property / cites work @@
+Nondeterministic Quantum Query and Communication Complexities
+Normal rank
@@ Property / cites work @@
+Common information and unique disjointness
@@ Property / cites work: Common information and unique disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+The matching polytope does not admit fully-polynomial size 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 @@
+Approximate Constraint Satisfaction Requires Large LP Relaxations
+Normal rank
@@ Property / cites work @@
+Extended formulations in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / 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 @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+A short proof that the extension complexity of the correlation polytope grows exponentially
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+A note on the extension complexity of the knapsack polytope
+Normal rank
@@ Property / cites work @@
+On the distributional complexity of disjointness
@@ Property / cites work: On the distributional complexity of disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+Some \(0/1\) polytopes need exponential size extended formulations
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank