Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
复制标题
有效减阻流、光谱稀疏树和不对称 TSP
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Gharan
中科院分区：
文献类型：
--
作者：
Nima Anari;S. Gharan
我们证明了非对称旅行商问题的自然 LP 松弛的完整性间隙是 polyloglog(n)。换句话说，存在一种多项式时间算法，该算法在polyloglog(n)的因子内逼近最佳巡视的值，其中polyloglog(n)是loglog(n)的有界次数多项式。我们通过证明任何 k 边连接的未加权图都具有 polyloglog(n)/k 薄生成树来证明这一点。我们的主要新成分是一个程序，尽管是一个指数大小的凸程序，它将不允许任何光谱稀疏树的图“转换”为那些可证明具有光谱稀疏树的图。更准确地说，给定 k 边连通图 G = (V, E)，其中 k ≥ 7 log(n)，我们证明存在一个矩阵 D，它“保留”G 所有割线的结构，使得对于导出 Ω(k) 边连通图的集合 F ⊆ E，F 中每条边的有效电阻D 至多是polylog(k)/k。然后，我们使用 Marcus、Spielman 和 Srivastava [1] 的开创性工作的扩展（在 [2] 中进行了充分解释）来证明相对于 D 的 polylog(k)/k-谱稀疏树的存在。这样的树相对于 G 是 polylog(k)/k-组合稀疏树，因为 D 保留了 G 的割结构。
We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n), where polyloglog(n) is a bounded degree polynomial of loglog(n). We prove this by showing that any k-edge-connected unweighted graph has a polyloglog(n)/k-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that “transforms” graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G = (V, E) where k ≥ 7 log(n), we show that there is a matrix D that “preserves” the structure of all cuts of G such that for a set F ⊆ E that induces an Ω(k)-edge-connected graph, the effective resistance of every edge in F w.r.t. D is at most polylog(k)/k. Then, we use our extension of the seminal work of Marcus, Spielman, and Srivastava [1], fully explained in [2], to prove the existence of a polylog(k)/k-spectrally thin tree with respect to D. Such a tree is polylog(k)/k-combinatorially thin with respect to G as D preserves the structure of cuts of G.