Incremental flow
Jeff Hartline, Alexa M. Sharp · Networks · 2007
Abstract This paper defines an incremental version of the maximum flow problem. In this model, the capacities increase over time and the resulting solution is a sequence of flows that build on each other incrementally. Thus far, incremental problems considered in the literature have been built on NP‐complete problems. To the best of our knowledge, our results are the first to find a polynomial time problem whose incremental version is NP‐complete. We present approximation algorithms and hardness results for many versions of this problem, and comment on the relation to multicommodity flow. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 77–85 2007