Title: Approximation Algorithms and Hardness of the kRoute Cut Problem Speaker: Yuan Zhou, CMU Inviter: Dr. Sun Xiaoming, Center for Advanced Computing Research, ICT Time: 11:00am12:00am, October 31th, 2011 (Monday) Place: Room 1201, Institute of Computing Technology, Chinese Academy of Sciences Abstract: We study the kroute cut problem: given an undirected edgeweighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of sourcesink pairs, and an integer connectivity requirement k, the goal is to find a minimumweight subset E' of edges to remove, such that the connectivity of each pair (s_i, t_i) falls below k. Specifically, in the edgeconnectivity version, ECkRC, the requirement is that there are at most (k1) edgedisjoint paths connecting s_i to t_i in G \ E', while in the vertexconnectivity version, VCkRC, the same requirement is for vertexdisjoint paths. Prior to our work, polylogarithmic approximation algorithm has been known for the special case where k=2, but no nontrivial approximation algorithms were known for any value k>2, except in the singlesource setting. We show an O(k log^{3/2}r)approximation algorithm for ECkRC with uniform edge weights, and several polylogarithmic bicriteria approximation algorithms for ECkRC and VCkRC, where the connectivity requirement k is violated by a constant factor. Our results improve the previously known result for the case k=2. We also prove that VCkRC is hard to approximate up to a factor of k^{\epsilon} for some fixed \epsilon>0. We then turn to study a simpler version of VCkRC, where only one sourcesink pair is present. We present a simple bicriteria approximation algorithm for this case. Then we show evidence that even this restricted version of the problem may be hard to approximate. For example, we show that the single sourcesink pair version of VCkRC has no constantfactor approximation, assuming Feige's Random kAND assumption. Joint work with Julia Chuzhoy, Yury Makarychev and Aravindan Vijayaraghavan. Bio: Yuan Zhou is a third year Ph.D. student at Carnegie Mellon University, supervised by Ryan O'Donnell and Venkatesan Guruswami. Before came to CMU he finished his undergraduate studies in the Special Pilot CS Class supervised by Prof. Andrew Yao at Institute for Theoretical Computer Science, Tsinghua University, China.
