A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
复制标题
用于平衡切割的确定性算法及其在动态连接、流等方面的应用
DOI：
10.1109/focs46700.2020.00111
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Saranurak, Thatchaphol
中科院分区：
文献类型：
--
作者：
Chuzhoy, Julia;Gao, Yu;Li, Jason;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol
我们考虑经典的最小平衡切割问题：给定一个图G，计算将其顶点划分为两个体积大致相等的子集，同时最小化连接子集的边的数量。我们提出了这个问题的第一个确定性的、几乎线性的时间逼近算法。具体来说，我们的算法，给定一个n顶点m边图G和任意参数1≤r≤O(logn)，在时间O(m1+O(1/r)+ O（1)·（logm）O(r2)）中计算G中最小平衡切的（logm）r2逼近。特别地，我们对任何常数在时间m1+O（√{ε}）上得到一个（logm）1/ε-近似，对任何缓慢增长的函数f(m)在时间m1+O(1)上得到一个（logm）f(m)-近似。对于最稀疏切割和最低电导切割问题，我们获得了具有类似保证的确定性算法。我们的最小平衡切割问题算法实际上提供了一个更强的保证：它要么返回一个接近给定目标值的平衡切割，要么通过展示一个具有高电导的G的大子图来证明这样的切割不存在。我们利用该算法获得了动态连通性和最小生成森林的确定性算法，其中n顶点图的最坏情况更新时间为no(1)，从而解决了动态图算法领域的一个主要开放问题。我们的工作也暗示了许多其他问题的确定性算法，这些问题的时间复杂性与已知的随机算法相匹配，高达n个因子的次多项式。其含义包括求解拉普拉斯系统和在无向图中近似最大流量的几乎线性时间确定性算法。
We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1 ≤ r ≤ O(logn), computes a (logm)r2-approximation for Minimum Balanced Cut in G, in time O(m1+O(1/r)+o(1)·(logm)O(r2)). In particular, we obtain a (logm)1/ε-approximation in time m1+O(√{ε})for any constant , and a (logm)f(m)-approximation in time m1+o(1), for any slowly growing function f(m). We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is no(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.
登录
查看更多内容
关于最稀疏割问题的割匹配博弈
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
R. Khandekar;Subhash Khot;L. Orecchia;Nisheeth K. Vishnoi
通讯作者：
Nisheeth K. Vishnoi
具有次多项式最坏情况更新时间的动态最小生成森林
DOI：
10.1109/focs.2017.92
发表时间：
2017
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Danupon Nanongkai;Thatchaphol Saranurak;Christian Wulff
通讯作者：
Christian Wulff
一种新的递减单源最短路径算法及其在顶点容量流和切割问题中的应用
DOI：
10.1145/3313276.3316320
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Julia Chuzhoy;S. Khanna
通讯作者：
S. Khanna
确定性递减单源最短路径：超出 o(mn) 界限
DOI：
10.1145/2897518.2897521
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
A. Bernstein;S. Chechik
通讯作者：
S. Chechik
DOI：
10.4230/lipics.icalp.2017.44
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
A. Bernstein
通讯作者：
A. Bernstein