Institutional Repository
| Unbalanced Graph Partitioning | |
| Li, Angsheng; Zhang, Peng | |
| 2013 | |
| Source | THEORY OF COMPUTING SYSTEMS
 |
| ISSN | 1432-4350 |
| Volume | 53Issue:3Pages:454-466 |
| English Abstract | 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). |
| Indexed Type | SCI |
| Keyword | Unbalanced Cut Sparsest Cut Network Community Social Networks Approximation Algorithms |
| Department | [Li, Angsheng] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China. [Zhang, Peng] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China. |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16912 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment