Approximation Algorithms for Unique Games
| COMPUTER SCIENCE/DISCRETE MATH, II | |
| Topic: | Approximation Algorithms for Unique Games |
| Speaker: | Luca Trevisan |
| Affiliation: | University of California, Berkeley |
| Date: | Tuesday, May 31 |
| Time/Room: | 11:30am - 12:30pm/S-101 |
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. Recent work has shown that the conjecture implies a number of very strong inapproximability results, including tight results for Max Cut and Vertex Cover. Generalizations of the conjecture to the case of sub-constant epsilon have also been considered, and shown to imply inapproximability results for Sparsest Cut and other problems.
We show that a strong generalization of the conjecture to sub-constant epsilon 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)) fraction of constraints, we can find in polynomial time an assignment that satisfies 99% of the constraints.
Feige and Reichman have shown that the problem of finding a solution that maximizes the number of satisfied constraints is hard to approximate within a 2^{(log n)^.99} factor, and so our work shows that the promise that the system is almost satisfiable changes its approximability a lot.