首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Fast and Deterministic Approximations for k-Cut
  • 本地全文:下载
  • 作者:Kent Quanrud
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2022
  • 卷号:18
  • 页码:1-24
  • DOI:10.4086/toc.2022.v018a007
  • 语种:English
  • 出版社:University of Chicago
  • 摘要:In an undirected graph, a k-cut is a set of edges whose removal breaks the graph into at least k connected components. The minimum-weight k-cut can be computed in n O(k) time, but when k is treated as part of the input, computing the minimum-weight k-cut is NPhard [Goldschmidt and Hochbaum 1994]. For poly(m,n, k)-time algorithms, the best possible approximation factor is essentially 2 under the Small-Set Expansion Hypothesis [Manurangsi 2017]. Saran and Vazirani [1995] showed that a (2−2/k)-approximately minimum-weight k-cut can be computed via O(k) minimum cuts, which implies a O˜(km) randomized running time via the nearly linear-time randomized min-cut algorithm of Karger [2000]. Nagamochi and Kamidoi [2007] showed that a (2 − 2/k)-approximately minimum-weight k-cut can be computed deterministically in O(mn + n 2 logn) time. These results prompt two basic questions. The first concerns the role of randomization. Is there a deterministic algorithm for 2-approximate minimum k-cut, matching the randomized running time of O˜(km)? The second question qualitatively compares minimum cut to 2-approximate minimum k-cut. Can 2-approximate minimum k-cut be computed as fast as the minimum cut, in O˜(m) randomized time?
  • 关键词:k-cut;multiplicative weight updates
国家哲学社会科学文献中心版权所有