A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
复制标题
低阈值秩图的新正则引理和更快的逼近算法
DOI：
10.1007/978-3-642-40328-6_22
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
S. Gharan;L. Trevisan
Kolla 和 Tulsiani [KT07、Kol11] 以及 Arora、Barak 和 Steurer [ABS10] 介绍了子空间枚举技术，该技术给出了图问题的近似算法，例如独特博弈和小集扩展；此类算法的运行时间在图的阈值秩中呈指数增长。
Kolla and Tulsiani [KT07, Kol11] and Arora, Barak and Steurer [ABS10] introduced the technique of subspace enumeration, which gives approximation algorithms for graph problems such as unique games and small set expansion; the running time of such algorithms is exponential in the threshold-rank of the graph.