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