Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Mordecai J. Golin, Hadi Khodabande, Bo Qin

Dynamic Flows were introduced by Ford and Fulkerson in 1958 to model flows over time. They define edge capacities to be the total amount of flow that can enter an edge {\em in one…