CS 789 THEORY SEMINAR [home]

Speaker:    Alexa Sharp, Cornell University
Date:          February 14, 2005
Title:          Incremental Flow

Abstract:

Have you ever wondered what chump was responsible for discontinuing the Ithaca-Pittsburgh flight? While the culprit may never be known, we do know they didn't use our incremental flow model for their flight scheduling.

In this talk we define an incremental version of the maximum flow problem, in which edge capacities increase over time and the desired solution is a sequence of flows that build on eachother incrementally. Any flow problem in which constraints rise over time and rerouting flow carries an implicit cost would benefit from this type of incremental model. The canonical example of flight scheduling, where discontinuing a flight leg is undesirable, is one such application.

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 several versions of this problem, and comment on the relation to multicommodity flow.

Joint work with Jeff Hartline.

A copy of the paper can be found on www.cs.cornell.edu/~asharp.