Optimization Online


An Efficient Algorithm for Computing Robust Minimum Capacity s-t Cuts

Doug Altner (daltner***at***gatech.edu)
Ozlem Ergun (oergun***at***isye.gatech.edu)

Abstract: The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit mining or scheduling jobs on two processors. In this paper, we present an efficient algorithm for computing minimum capacity s-t cuts under a polyhedral model of robustness. Our algorithm builds on the idea of the general algorithm of Bertsimas and Sim for solving robust combinatorial optimization problems (RobuCOPs). We demonstrate that our algorithm is fast when compared to a naive algorithm that uses a black-box maximum flow solver as a subroutine. Specifically, we demonstrate that our implementation can solve instances of the robust minimum s-t cut problem in seconds whereas an implementation using a black-box maximum flow solver would take hours.

Keywords: Minimum Capacity Cut, Robust Optimization, Maximum Flow Reoptimization

Category 1: Network Optimization

Category 2: Robust Optimization

Citation: H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Technical Report March, 2008.


Entry Submitted: 03/20/2008
Entry Accepted: 03/21/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