SDP gaps and UGC-hardness for max-cut-gain

DOI10.4086/TOC.2009.V005A004zbMATH Open1213.68313OpenAlexW1591762700MaRDI QIDQ3002802FDOQ3002802

Authors: Subhash Khot, Ryan O'Donnell 

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2009.v005a004

Recommendations

• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the optimality of the random hyperplane rounding technique for MAX CUT
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the integrality ratio of semidefinite relaxations of MAX CUT

zbMATH Keywords

quadratic programmingsemidefinite programmingFourier analysismax-cutunique games conjectureGrothendieck inequalityGaussian spacedictator testingmax-cut-gainsemidefinite programming gaps

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Cited In (11)

• Grothendieck-type inequalities in combinatorial optimization
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Approximating sparse quadratic programs
• Mathematics of computation through the lens of linear equations and lattices
• Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
• The power of unentangled quantum proofs with non-negative amplitudes
• SDP gaps for 2-to-1 and other Label-Cover variants
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• The positive semidefinite Grothendieck problem with rank constraint

This page was built for publication: SDP gaps and UGC-hardness for max-cut-gain

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