Unbalanced Graph Partitioning
文献类型：期刊论文
| 作者 | Li, Angsheng ; Zhang, Peng |
| 刊名 | THEORY OF COMPUTING SYSTEMS
 |
| 出版日期 | 2013 |
| 卷号 | 53期号:3页码:454-466 |
| 关键词 | Unbalanced cut Sparsest cut Network community Social networks Approximation algorithms |
| ISSN号 | 1432-4350 |
| 中文摘要 | 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. We consider two closely related unbalanced cut problems, in which the quality of a cut is measured with respect to 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))-bicriteria approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance). |
| 英文摘要 | 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. We consider two closely related unbalanced cut problems, in which the quality of a cut is measured with respect to 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))-bicriteria approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance). |
| 收录类别 | SCI |
| 语种 | 英语 |
| 公开日期 | 2014-12-16 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16912]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Li, Angsheng,Zhang, Peng. Unbalanced Graph Partitioning[J]. THEORY OF COMPUTING SYSTEMS,2013,53(3):454-466. |
| APA | Li, Angsheng,&Zhang, Peng.(2013).Unbalanced Graph Partitioning.THEORY OF COMPUTING SYSTEMS,53(3),454-466. |
| MLA | Li, Angsheng,et al."Unbalanced Graph Partitioning".THEORY OF COMPUTING SYSTEMS 53.3(2013):454-466. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。