标题:Unbalanced Graph Partitioning
作者:Li, Angsheng; Zhang, Peng
通讯作者:Li, A
作者机构:[Zhang, Peng] Shandong Univ, Sch Comp Sci, Jinan 250101, Peoples R China.; [Li, Angsheng] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, B 更多
会议名称:21st Annual International Symposium on Algorithms and Computations (ISAAC)
会议日期:DEC 15-17, 2010
来源:ALGORITHMS AND COMPUTATION, PT I
出版年:2010
卷:6506
期:PART 1
页码:218-229
DOI:10.1007/978-3-642-17517-6_21
摘要:We investigate the unbalanced cut problems. A cut (A, B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size), where k is an input parameter. An s-t cut (A, B) is called unbalanced if its s-side is of k-size or Ek-size. We consider three types of unbalanced cut problems, in which the quality of a cut is measured with respect to the capacity, the sparsity, and the conductance, respectively.; We show that even if the input graph is restricted to be a tree, the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard. We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most O(log n) times the optimum and whose smaller side has size at most O(log n)k. As a consequence, this leads to a (O(log n), O(log n))-approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance). We also prove that the Min k-Size s-t Cut problem is NP-hard and give an O(log n)-approximation algorithm for it.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:5
Scopus被引频次:8
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-78650881877&doi=10.1007%2f978-3-642-17517-6_21&partnerID=40&md5=2c9936d197c196f7ef2a806e6901f0cd
TOP