Towards strong nonapproximability results in the Lovász-Schrijver hierarchy

DOI10.1007/s00037-011-0027-zzbMath1252.68131OpenAlexW2007239493MaRDI QIDQ430828

Iannis Tourlakis, Michael Alekhnovich, Sanjeev Arora

Publication date: 26 June 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0027-z

zbMATH Keywords

approximation algorithmNP-complete problemslower boundsproof complexitylift and project methodsmatrix cut operatorsrandom instances of 3SAT

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

The Power of Sherali--Adams Relaxations for General-Valued CSPs, Sparsification and subexponential approximation, Unnamed Item, Sherali-adams strikes back, Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• A threshold of ln n for approximating set cover
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• On the power of unique 2-prover 1-round games
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interactive proofs and the hardness of approximating cliques
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Integrality gaps for Sherali-Adams relaxations
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Some optimal inapproximability results
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• Expander flows, geometric embeddings and graph partitioning