Fault-Tolerance in Buy-at-Bulk and Hop-Constrained Network Design

Host
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 node pairs. In this problem, the cost of purchasing capacity on an edge is given by a sub-additive function, thus capturing settings that exhibit economies of scale. In the fault-tolerant setting, the goal is to protect against node or edge failures by instead sending flow for each demand pair on k disjoint paths. Despite substantial work addressing various special cases, there is still no nontrivial approximation algorithm known for fault-tolerant buy-at-bulk, even for protecting against a single edge failure (k=2)!
In this talk, I will highlight some recent progress in buy-at-bulk network design via a connection to hop-constrained network design. Leveraging recent progress in hop-constrained oblivious routing, we obtain several polylogarithmic approximation algorithms for hop-constrained network design problems, including a relaxed notion of fault-tolerance that is of independent interest. I will conclude by briefly discussing new algorithmic techniques towards resolving the fault-tolerant buy-at-bulk problem.
This talk is based on joint work with Chandra Chekuri.