TY - GEN
T1 - Approximate Lasserre integrality gap for unique games
AU - Khot, Subhash
AU - Popat, Preyas
AU - Saket, Rishi
PY - 2010
Y1 - 2010
N2 - In this paper, we investigate whether a constant round Lasserre Semi-definite Programming (SDP) relaxation might give a good approximation to the Unique Games problem. We show that the answer is negative if the relaxation is insensitive to a sufficiently small perturbation of the constraints. Specifically, we construct an instance of Unique Games with k labels along with an approximate vector solution to t rounds of the Lasserre SDP relaxation. The SDP objective is at least 1-ε whereas the integral optimum is at most γ, and all SDP constraints are satisfied up to an accuracy of δ>0. Here ε, γ>0 and t ∈ℤ+ are arbitrary constants and k=k(ε, γ) ∈ℤ+. The accuracy parameter δ can be made sufficiently small independent of parameters ε, γ, t, k (but the size of the instance grows as δ gets smaller).
AB - In this paper, we investigate whether a constant round Lasserre Semi-definite Programming (SDP) relaxation might give a good approximation to the Unique Games problem. We show that the answer is negative if the relaxation is insensitive to a sufficiently small perturbation of the constraints. Specifically, we construct an instance of Unique Games with k labels along with an approximate vector solution to t rounds of the Lasserre SDP relaxation. The SDP objective is at least 1-ε whereas the integral optimum is at most γ, and all SDP constraints are satisfied up to an accuracy of δ>0. Here ε, γ>0 and t ∈ℤ+ are arbitrary constants and k=k(ε, γ) ∈ℤ+. The accuracy parameter δ can be made sufficiently small independent of parameters ε, γ, t, k (but the size of the instance grows as δ gets smaller).
UR - http://www.scopus.com/inward/record.url?scp=78149346931&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78149346931&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15369-3_23
DO - 10.1007/978-3-642-15369-3_23
M3 - Conference contribution
AN - SCOPUS:78149346931
SN - 3642153682
SN - 9783642153686
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 298
EP - 311
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Y2 - 1 September 2010 through 3 September 2010
ER -