TITLE: Two Interesting Problems Involving Maximum Flows

SPEAKER: Doug Altner, Ph.D. Candidate,
H. Milton Stewart School of Industrial and Systems Engineering,
Georgia Institute of Technology

DATE / TIME: Friday, February 15, 2008 / 2:30 - 3:45 p.m.

LOCATION: Room 453 Mohler Lab, 200 W. Packer Avenue


ABSTRACT: The Maximum Flow Problem is a fundamental problem in operations research. This talk focuses on two problems involving computing a maximum flow. First, we present theoretical results on the Maximum Flow Network Interdiction Problem (MFNIP), where an interdictor seeks to remove arcs from a network so as to minimize the maximum flow in the remaining network. Second, we introduce an algorithm to rapidly solve an online sequence of similar maximum flow problems. As an application, we extend our algorithm to compute a robust minimum s-t cut, that is, a conservatively chosen minimum s-t cut in light of data uncertainty. We report the substantial reduction in running time from using our algorithm instead of repeatedly using an efficient black-box maximum flow solver.

BIOGRAPHY: Doug Altner is a doctoral candidate at the H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology. He graduated from Carnegie Mellon University’s Department of Mathematical Sciences in 1999 and in the same year began his doctoral study at Georgia Tech. His Ph.D. concentration is in optimization and he is writing his doctoral dissertation on theoretical and computational advancements on problems involving maximum flows. In addition to the above, his research interests include algorithms for combinatorial optimization, very large-scale neighborhood search and applications in defense, freight transportation and sports scheduling.