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

DOI10.1007/S00037-011-0027-ZzbMATH Open1252.68131OpenAlexW2007239493MaRDI QIDQ430828FDOQ430828

Authors: Michael Alekhnovich, Iannis Tourlakis, 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

Recommendations

• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• CSP gaps and reductions in the lasserre hierarchy
• Approximate Constraint Satisfaction Requires Large LP Relaxations

zbMATH Keywords

approximation algorithmlower boundsproof complexityNP-complete problemslift 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)

Cites Work

• 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
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Interactive proofs and the hardness of approximating cliques
• Title not available (Why is that?)
• Some optimal inapproximability results
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Expander flows, geometric embeddings and graph partitioning
• Linear programming relaxations of \textsc{maxcut}
• Proving integrality gaps without knowing the linear program
• Title not available (Why is that?)
• Integrality gaps for Sherali-Adams relaxations
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Rank bounds and integrality gaps for cutting planes procedures
• Title not available (Why is that?)
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited In (8)

• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Sherali-adams strikes back
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The power of Sherali-Adams relaxations for general-valued CSPs
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Title not available (Why is that?)
• Sparsification and subexponential approximation

This page was built for publication: Towards strong nonapproximability results in the Lovász-Schrijver hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q430828)