Efficient Dynamic Network Flow Algorithms

Abstract

Dynamic network flows model transportation. A dynamic network consists of a graph with capacities and transit times on its edges. Flow moves through a dynamic network over time. Edge capacities restrict the rate of flow and edge transit times determine how long each unit of flow spends traversing the network. Dynamic network flows have been studied extensively for decades.

This thesis introduces the first polynomial algorithms to solve several important dynamic network flow problems. We solve them by computing chain-decomposable flows, a new class of structured dynamic flows.

We solve the quickest transshipment problem. An instance of this problem consists of a dynamic network with several sources and sinks. Each source has a specified supply and each sink a specified demand of flow. The goal is to move the appropriate amount of flow out of each source and into each sink within the least overall time. Previously, this problem could only be solved efficiently in the special case of a single source and single sink.

Our quickest transshipment algorithm depends on efficient solutions to the dynamic transshipment problem and the lexicographically maximum dynamic flow problem. The former is a version of the quickest transshipment problem in which the time bound is specified. The latter is a maximum flow problem in a dynamic network with prioritized sources and sinks; the goal is to maximize the amount of flow leaving each high-priority subset of sources and sinks.

We also consider the universally maximum dynamic flow problem. A universally maximum dynamic flow sends flow between a source and sink so that the sink receives flow as quickly as possible; subject to that, the source releases flow as late as possible. We describe the first polynomial algorithm to approximate a universally maximum dynamic flow within a factor of $(1+\eps)$, for any $\eps>0$. We also describe the first polynomial algorithm to compute the value of a universally maximum dynamic flow at a single specified moment of time.