How to Play Unique Games on Expanders

Simple item page
dc.creatorMakarychev, Konstantin
dc.creatorMakarychev, Yury
dc.date2009-03-02
dc.date.accessioned2026-07-07T12:48:13Z
dc.date.available2026-07-07T12:48:13Z
dc.descriptionIn 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-\varepsilon)$-satisfiable instance of Unique Games with the constraint graph $G$, our algorithm finds an assignment satisfying at least a $1- C \varepsilon/h_G$ fraction of all constraints if $\varepsilon < c λ_G$ where $h_G$ is the edge expansion of $G$, $λ_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.
dc.identifierhttps://arxiv.org/abs/0903.0367
dc.identifierhttp://arxiv.org/abs/0903.0367
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/221981
dc.subjectData Structures and Algorithms
dc.titleHow to Play Unique Games on Expanders
dc.typetext

Files

Collections

arXiv