ECCC-Report TR05-034https://eccc.weizmann.ac.il/report/2005/034Comments and Revisions published for TR05-034en-usSun, 18 Sep 2005 00:00:00 +0300
Revision 1
| Approximation Algorithms for Unique Games |
Luca Trevisan
https://eccc.weizmann.ac.il/report/2005/034#revision1We 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.
Sun, 18 Sep 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/034#revision1
Comment 1
| |
Luca Trevisan
https://eccc.weizmann.ac.il/report/2005/034#comment1We 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.
Fri, 13 May 2005 20:52:42 +0300https://eccc.weizmann.ac.il/report/2005/034#comment1
Paper TR05-034
| Approximation Algorithms for Unique Games |
Luca Trevisan
https://eccc.weizmann.ac.il/report/2005/034Khot 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."
Wed, 06 Apr 2005 22:49:30 +0300https://eccc.weizmann.ac.il/report/2005/034