Grainger College of Engineering, All Events

Abstract:  Buy-at-bulk network design is a classical and practically motivated problem, in which the goal is to construct a low-cost network that supports multi-commodity flow between given demand pairs of vertices. In this problem, the cost of purchasing capacity on an edge is given by a sub-additive function, capturing settings that exhibit economies of scale. The fault-tolerant problem aims to protect against node or edge failures by sending flow for each demand pair along disjoint paths. Despite substantial work addressing various special cases, no polylogarithmic approximation was previously known, even for protecting against a single edge failure!

We resolve this open problem by leveraging connections to length-constrained network design; this is an area of independent interest that imposes constraints on the length of paths used to connect demand pairs. In this talk, I will introduce two natural definitions of fault tolerance in length-constrained network design and present the high-level ideas for polylogarithmic approximations for these problems, in turn yielding the first polylogarithmic approximation for fault-tolerant buy-at-bulk.

Bio: Rhea Jain is a 5th year PhD student at the University of Illinois Urbana-Champaign advised by Prof. Chandra Chekuri.