Flows over Time

Lisa Fleischer
Carnegie Mellon University, Pittsburgh, PA


Flows over time generalize traditional network flow problems by introducing the element of time. This allows for modelling a much broader class of problems, but at a cost --- flow over time problems are more difficult and less well understood than traditional network flow problems. Recent progress in developing effective techniques for solving these problems has led to the first polynomial time algorithms with provable solution guarantees for a large class of separated continuous linear programs. This class includes fluid relaxations of control problems in queueing networks. We will survey the field of flows over time, presenting some classic and recent results while describing the basic difficulties and techniques. We will demonstrate the use of some of these techniques in approximation schemes for fluid relaxations of queueing networks.