How to Play Unique Games on Expanders

Details How to Play Unique Games on Expanders How to Play Unique Games on Expanders

2009-03-02

arxiv.org/abs/0903.0367v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 \lambda_G$ where $h_G$ is the edge expansion of $G$, $\lambda_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.

Affiliated with

Also associated with

No associations

Rating

How to Play Unique Games on Expanders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How to Play Unique Games on Expanders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to Play Unique Games on Expanders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-651715