Rapidly Solving an Online Sequence of Maximum Flow Problems

Douglas Altner (daltnergatech.edu)
Ozlem Ergun (oergunisye.gatech.edu)

Abstract: We investigate how to rapidly solve an online sequence of maximum flow problems. Sequences of maximum flow problems arise in a diverse collection of settings, including stochastic network programming and real-time scheduling of jobs on a two-processor computer. In this paper, we formulate solving an online sequence of maximum flow problems as the Maximum Flow Reoptimization Problem, introduce a maximum flow algorithm designed for ``warm starts,'' and present computational results.

Keywords: Maximum Flow, Warm Starting, Online Sequence, Goldberg-Tarjan Algorithm

Category 1: Network Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, March, 2008.

Download:

Entry Submitted: 01/11/2008
Entry Accepted: 01/11/2008
Entry Last Modified: 04/04/2008

Modify/Update this entry