Optimization Online


Rapidly Solving an Online Sequence of Maximum Flow Problems

Douglas Altner (daltner***at***gatech.edu)
Ozlem Ergun (oergun***at***isye.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.


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society