Near-optimal algorithms for unique games
Near-optimal algorithms for unique games
复制标题
独特游戏的近乎最佳算法
DOI：
10.1145/1132516.1132547
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yury Makarychev
中科院分区：
文献类型：
--
作者：
M. Charikar;K. Makarychev;Yury Makarychev
独特的游戏是约束满足问题，可以被看作是一个推广的最大切割到一个更大的域大小。唯一博弈猜想指出，很难区分几乎所有约束都可满足的唯一博弈实例和几乎没有约束可满足的唯一博弈实例。它已被证明意味着一些不可逼近的基本问题，似乎很难获得更标准的复杂性假设的结果。因此，证明或反驳这个猜想是一个重要的目标。我们提出了显着改进的近似算法独特的游戏。对于最优解满足所有约束的1-ε分数的域大小为k的情况，我们的算法大致满足所有约束的k-ε/（2-ε）和1- O（εlog k）分数。我们的算法是基于四舍五入的自然半定规划松弛的问题，其性能几乎匹配的完整性差距，这种松弛。如果唯一博弈猜想成立，我们的结果接近最优，即任何改进（超出低阶项）都将反驳该猜想。
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. It has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. Thus, proving or refuting this conjecture is an important goal. We present significantly improved approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1-ε fraction of all constraints, our algorithms satisfy roughly k-ε/(2-ε) and 1- O(√εlog k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.