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

DOI10.4086/TOC.2009.V005A004MaRDI QIDQ3002802zbMATHOpenAlexFDO

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

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)

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

Cited in

(12)

• Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
• On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension
• Grothendieck-type inequalities in combinatorial optimization
• Approximating sparse quadratic programs
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• The power of unentangled quantum proofs with non-negative amplitudes
• The positive semidefinite Grothendieck problem with rank constraint
• Mathematics of computation through the lens of linear equations and lattices
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• SDP gaps for 2-to-1 and other Label-Cover variants
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• Pseudorandom sets in Grassmann graph have near-perfect expansion

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)