Algorithm and Information Colloquium (AIC)

Title:　　　  Unbalanced Graph Partitioning

Speaker:　 Peng Zhang 张鹏

Time:　　　　  16:30 – 17:30, June 30, 2010, Wednesday

Place:　　　　 Lecture Room, Level 3, Building No. 5, Institute of Software

Tea time:　　 16:00 – 16:30, Common Room, Level 3, Building No. 5

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 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.

1) 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.
2) 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), which has particular applications in the identification of community structure in social networks.

This is a joint work with Prof. Angsheng Li. The speaker is supported in part by the StarTrack Program of Microsoft Research Asia.

Biography:

Peng ZHANG, got his Ph.D. degree in computer science from Institute of Software, Chinese Academy of Sciences, under the supervision of Prof. Angsheng Li. He is currently a faculty member of School of Computer Science and Technology, Shandong University. His research interests mainly include approximation algorithms and combinatorial optimization.