Capacitated Network Design: Algorithms and Hardness

October 9, 2013

In this talk, we will discuss the following network design problem: we are given a multicommodity demand D (or a collection of source-sink pairs each with a routing requirement), and a capacitated graph. The goal is to pick the "smallest subgraph" so that the given demand can be completely routed. This basic problem is a crucial subroutine for many algorithmic problems, such as buy-at-bulk, energy-minimizing routing, etc. Our understanding, however, is limited, even for the case of one demand pair, which is the classical s-t flow problem. In this talk, we survey what we know about this problem and present some recent algorithmic results for special cases and hardness results.

*Based on joint works with A. Antoniodis, D. Chakrabarty, S. Im, S. Li, B. Moseley, V. Nagarajan, S. Narayanan, K. Pruhs, and C. Stein*