期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Approximation algorithm , edge expansion , expander , Unique Games
