How to Play Unique Games on Expanders

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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-\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.

Keywords

Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/221981

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0903.0367
 http://arxiv.org/abs/0903.0367

Collections

arXiv