Title: Approximation Algorithms and Hardness of the k-Route Cut Problem
Speaker: Yuan Zhou, CMU
Inviter: Dr. Sun Xiaoming, Center for Advanced Computing Research, ICT
Time: 11:00am-12:00am, October 31th, 2011 (Monday)
Place: Room 1201, Institute of Computing Technology, Chinese Academy of Sciences
Abstract:
We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of each pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithm has been known for the special case where k=2, but no non-trivial approximation algorithms were known for any value k>2, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, 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 VC-kRC 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 VC-kRC, where only one source-sink pair is present. We present a simple bi-criteria 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 source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige's Random k-AND 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.