Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

DOI10.1109/FOCS.2009.73zbMath1292.90230OpenAlexW2151395725MaRDI QIDQ5171221

David Steurer, Prasad Raghavendra

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.73

Mathematics Subject Classification ID

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

Related Items (19)

Making the Long Code Shorter ⋮ Unnamed Item ⋮ An introduction to the Ribe program ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Spectral algorithms for unique games ⋮ Unnamed Item ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Cones of multipowers and combinatorial optimization problems ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ Semidefinite Programming and Constraint Programming ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Unnamed Item ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES