No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

DOI10.1287/moor.2017.0918zbMath1435.68110arXiv1503.00753OpenAlexW2892107877MaRDI QIDQ5219712

Sebastian Pokutta, Samuel Fiorini, Abbas Bazzi, Ola Svensson

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.00753

zbMATH Keywords

linear programmingindependent setvertex coverhardness of approximationextended formulations

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (13)

Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ The matching problem has no small symmetric SDP ⋮ Affine reductions for LPs and SDPs ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Fixed cardinality stable sets ⋮ The k-Observer Problem on d-regular Graphs ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Integrality gap of the vertex cover linear programming relaxation ⋮ Extended formulations from communication protocols in output-efficient time ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Set-weighted games and their application to the cover problem ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem ⋮ New limits of treewidth-based tractability in optimization

Cites Work

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

This page was built for publication: No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ