Approximation Algorithms and Hardness for Strong Unique Games
Approximation Algorithms and Hardness for Strong Unique Games
The Unique Games problem is a central problem in algorithms and complexity theory. Given an instance of Unique Games, the Strong Unique Games problem asks to find the largest subset of vertices, such that the Unique Games instance induced on them is completely satisfiable. In this work, we give new …