How to Play Unique Games on Expanders

DOI10.1007/978-3-642-18318-8_17MaRDI QIDQ3075461zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev

Publication date 15 February 2011

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.0367

Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: 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 - v a r e p s i l o n)

-satisfiable instance of Unique Games with the constraint graph

G

, our algorithm finds an assignment satisfying at least a

1 - C v a r e p s i l o n / h_{G}

fraction of all constraints if

v a r e p s i l o n < c l a m b d a_{G}

where

h_{G}

is the edge expansion of

G

,

l a m b d a_{G}

is the second smallest eigenvalue of the Laplacian of

G

, and

C

and

c

are some absolute constants.

Recommendations

Cited in

(13)

This page was built for publication: How to Play Unique Games on Expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075461)