No Small Linear Program Approximates Vertex Cover Within a Factor 2 − <i>ɛ</i> (Q5219712): Difference between revisions

@@ Property / cites work @@
+Q3002764
@@ Property / cites work: Q3002764 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Long Code Test with One Free Bit
@@ Property / cites work: Optimal Long Code Test with One Free Bit / rank @@
+Normal rank
@@ Property / cites work @@
+Sum of Squares Lower Bounds from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+Q2913812
@@ Property / cites work: Q2913812 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743407
@@ Property / cites work: Q5743407 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate formulations for 0-1 knapsack sets
@@ Property / cites work: Approximate formulations for 0-1 knapsack sets / rank @@
+Normal rank
@@ Property / cites work @@
+Common information and unique disjointness
@@ Property / cites work: Common information and unique disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+Inapproximability of Combinatorial Problems via Small LPs and SDPs
+Normal rank
@@ Property / cites work @@
+Strong reductions for extended formulations
@@ Property / cites work: Strong reductions for extended formulations / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Limits of Linear Programs (Beyond Hierarchies)
+Normal rank
@@ Property / cites work @@
+On the existence of 0/1 polytopes with high semidefinite extension complexity
+Normal rank
@@ Property / cites work @@
+Integrality gaps for Sherali-Adams relaxations
@@ Property / cites work: Integrality gaps for Sherali-Adams relaxations / rank @@
+Normal rank
@@ Property / cites work @@
+Extended formulations in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Q2934582
@@ Property / cites work: Q2934582 / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+Demand Queries with Preprocessing
@@ Property / cites work: Demand Queries with Preprocessing / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive proofs and the hardness of approximating cliques
+Normal rank
@@ Property / cites work @@
+Exponential Lower Bounds for Polytopes in Combinatorial Optimization
+Normal rank
@@ Property / cites work @@
+Optimal Sherali-Adams Gaps from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Symmetry Matters for the Sizes of Extended Formulations
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+SDP Integrality Gaps with Local ell_1-Embeddability
+Normal rank
@@ Property / cites work @@
+Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
+Normal rank
@@ Property / cites work @@
+Q4537750
@@ Property / cites work: Q4537750 / rank @@
+Normal rank
@@ Property / cites work @@
+Global Optimization with Polynomials and the Problem of Moments
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+An information complexity approach to extended formulations
+Normal rank
@@ Property / cites work @@
+Noise stability of functions with low influences: invariance and optimality
+Normal rank
@@ Property / cites work @@
+Analysis of Boolean Functions
@@ Property / cites work: Analysis of Boolean Functions / rank @@
+Normal rank
@@ Property / cites work @@
+Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
+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 @@
+Q3549626
@@ Property / cites work: Q3549626 / rank @@
+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 @@
+Q3191594
@@ Property / cites work: Q3191594 / rank @@
+Normal rank
@@ Property / cites work @@
+CSP gaps and reductions in the lasserre hierarchy
@@ Property / cites work: CSP gaps and reductions in the lasserre hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank