| Title: | unbalanced graph partitioning |
| Author: | Li Angsheng
; Zhang Peng
|
| Source: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| Conference Name: | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
|
| Conference Date: | 40878
|
| Issued Date: | 2010
|
| Conference Place: | Jeju Island, Korea, Republic of
|
| Keyword: | Computational complexity
; Trees (mathematics)
|
| Publish Place: | Germany
|
| Indexed Type: | EI
|
| ISSN: | 3029743
|
| ISBN: | 3642175163
|
| Department: | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) School of Computer Science and Technology, Shandong University, Jinan 250101, China
|
| Sponsorship: | Spec. Interest Group Theor. Comput. Sc. (SIGTCS); Korean Inst. Inf. Sci. Eng. (KIISE)
|
| 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. 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(logn) times the optimum and whose smaller side has size at most O(logn)k. As a consequence, this leads to a (O(logn), O(logn))- 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(logn)-approximation algorithm for it. © 2010 Springer-Verlag. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/8958
|
| Appears in Collections: | 计算机科学国家重点实验室 _会议论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| unbalanced graph partitioning.pdf（221KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
Li Angsheng,Zhang Peng. unbalanced graph partitioning[C]. 见:21st Annual International Symposium on Algorithms and Computations, ISAAC 2010. Jeju Island, Korea, Republic of. 40878.
|
|
|
