Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-034 | 18th September 2005 00:00

Approximation Algorithms for Unique Games

RSS-Feed




Revision #1
Authors: Luca Trevisan
Accepted on: 18th September 2005 00:00
Downloads: 4021
Keywords: 


Abstract:

We present a polynomial time algorithm based on semidefinite programming that,
given a unique game of value $1-O(1/\log n$), satisfies
a constant fraction of constraints, where $n$ is the
number of variables. For sufficiently large alphabets, it improves an algorithm
of Khot (STOC'02) that satisfies a constant fraction of
constraints in unique games of value $1-c/(k^{10}(\log k)^5)$,
where $k$ is the size of the alphabet. We also present
a simpler algorithm for the special case of unique
games with linear constraints, and a combinatorial algorithm
for the general case.

Finally, we present a simple approximation algorithm for 2-to-1 games.


Paper:

TR05-034 | 5th April 2005 00:00

Approximation Algorithms for Unique Games





TR05-034
Authors: Luca Trevisan
Publication: 6th April 2005 22:49
Downloads: 3414
Keywords: 


Abstract:

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an epsilon fraction of constraints. We show that a strong generalization of the conjecture fails. Namely, we show that, given a system of constraints and the promise that there is an assignment that satisfies a 1-1/O((log n)^3) fraction of constraints, we can find in polynomial time an assignment that satisfies 99% of the constraints. If the constraints are linear, then given a system and the promise that a 1-1/O(log n) fraction of constraints are satisfiable, we can satisfy a 99% fraction in polynomial time. We also show weaker results about "2-to-1 Games."


Comment(s):

Comment #1 to TR05-034 | 13th May 2005 20:52





Comment #1
Authors: Luca Trevisan
Accepted on: 13th May 2005 20:52
Downloads: 3642
Keywords: 


Abstract:

We present a polynomial time algorithm that,
given a unique game of value $1-c/\log n$, satisfies
a constant fraction of constraints, where $n$ is the
number of variables.

This improves an algorithm of Trevisan (ECCC TR05-34), that
satisfies a constant fraction of constraints in unique games of value $1-c/(\log n)^3$
and, for sufficiently large alphabets, it improves an algorithm
of Khot (STOC'02) that satisfies a constant fraction of
constraints in unique games of value $1-c/(k^{10}(\log k)^5)$,
where $k$ is the size of the alphabet.

The result presented in this note will be incorporated in a later
version of ECCC TR05-34.




ISSN 1433-8092 | Imprint