Visiting Speaker
Date: Monday, July 19, 2010, 11 am, 223 SB
Title: Approximability of Capacitated Network Design
Speaker: Nitish Korula - UIUC
Abstract
In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood; in this talk, we present several new results and insights into the approximability of Cap-SNDP.
We give an O(log n) approximation for a special case of Cap-SNDP where the global minimum cut is required to be at least R; this generalizes the well known minimum-cost k-edge-connected subgraph problem. Our result is based on rounding a strengthening of a natural cut-based LP relaxation. This technique extends to give a similar approximation for a new network design problem that captures global minimum cut as a special case. We then show that as we move away from global connectivity, even for the single pair case (that is, when only one pair (s, t) has positive connectivity requirement), the problem appears to be harder. Our strengthened LP has an Ω(n) integrality gap, and one can prove hardness results in both directed and undirected graphs.
We also consider a variant of the Cap-SNDP in which multiple copies of an edge can be bought: we give an O(log k) approximation for this case, where k is the number of vertex pairs with non-zero connectivity requirement.
Joint work with Deeparnab Chakrabarty, Chandra Chekuri, and Sanjeev Khanna
Biography
Nitish Korula is a Ph.D. candidate in Computer Science at the University of Illinois, Urbana-Champaign, where he is the most recent recipient of the University of Illinois Dissertation Completion Fellowship; previously, he completed his B.E. at Birla Institute of Technology & Science, Pilani, India. After completing his Ph.D., he will be joining Google Research in September 2010. His research is primarily on effective algorithms for optimization problems; particular interests are the fields of approximation and online algorithms, and graph theory.