In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C epsilon/h) fraction of all constraints if epsilon < c lambda where h is the edge expansion of G, lambda is the second smallest eigenvalue of the Laplacian of G, and C and c are some absolute constants.
展开▼
