Spectral Algorithms for Unique Games
Spectral Algorithms for Unique Games
复制标题
独特游戏的谱算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Kolla
中科院分区：
文献类型：
--
作者：
A. Kolla
我们给出了一个新的算法，独特的游戏，这是基于纯粹的频谱技术，在该地区，这在很大程度上依赖于半定规划（SDP）以前的工作相比。给定一个高度可满足的独特游戏实例，我们的算法能够恢复一个很好的分配。近似保证只依赖于游戏的完整性，而不是字母表的大小，而运行时间取决于标签扩展图的谱特性与独特的游戏的实例，我们进一步表明，输入Khot和Vishnoi的完整性差距的情况下，我们的算法运行在准多项式时间，并决定该实例是高度不可满足的。值得注意的是，当在此实例上运行时，Unique Games的标准SDP松弛失败。作为一种特殊情况，我们还重新推导了一个多项式时间算法的唯一游戏扩展约束图。我们的算法的主要成分是一种技术，有效地利用整个频谱的基础图，而不仅仅是第二个特征值，这是独立的利益。如何在算法设计中利用图的全谱的问题经常被研究，但在此之前没有取得重大进展。
We give a new algorithm for Unique Games which is based on purely spectral techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the Label-Extended graph associated with the instance of Unique Games.We further show that on input the integrality gap instance of Khot and Vishnoi, our algorithm runs in quasi-polynomial time and decides that the instance is highly unsatisfiable. Notably, when run on this instance, the standard SDP relaxation of Unique Games fails. As a special case, we also re-derive a polynomial time algorithm for Unique Games on expander constraint graphs.The main ingredient of our algorithm is a technique to effectively use the full spectrum of the underlying graph instead of just the second eigenvalue, which is of independent interest. The question of how to take advantage of the full spectrum of a graph in the design of algorithms has been often studied, but no significant progress was made prior to this work.