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

DOI10.1007/S00037-011-0027-ZMaRDI QIDQ430828zbMATHOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 5899254 (Why is no real title available?)
• scientific article; zbMATH DE number 5485464 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A threshold of ln n for approximating set cover
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Expander flows, geometric embeddings and graph partitioning
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Integrality gaps for Sherali-Adams relaxations
• Interactive proofs and the hardness of approximating cliques
• Linear programming relaxations of \textsc{maxcut}
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Proving integrality gaps without knowing the linear program
• Rank bounds and integrality gaps for cutting planes procedures
• Some optimal inapproximability results
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Cited in

(8)

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

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)