How to Play Unique Games Using Embeddings
How to Play Unique Games Using Embeddings
复制标题
如何使用嵌入玩独特的游戏
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yury Makarychev
中科院分区：
文献类型：
--
作者：
E. Chlamtác;K. Makarychev;Yury Makarychev
在本文中，我们提出了一种新的近似算法，用于独特游戏。对于具有N顶点和K状态（标签）的唯一游戏，如果满足所有约束的A（1- epsiv）部分，则该算法会找到满足1 -O（Epsiv radic（log n log k））的任务所有约束。为此，我们介绍了新的嵌入技术，用于四舍五入的半决赛放松较大域大小的问题
In this paper we present a new approximation algorithm for unique games. For a unique game with n vertices and k states (labels), if a (1 - epsiv) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(epsiv radic(log n log k)) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size