Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems

Douglas Altner () and Özlem Ergun ()

Annals of Operations Research, 2011, vol. 184, issue 1, 3-26

Abstract: The Minimum Capacity s-t Cut Problem (MinCut) is an intensively studied problem in combinatorial optimization. A natural extension is the problem of choosing a minimum capacity s-t cut when arc capacities are unknown but confined to known intervals. This motivates the Robust Minimum Capacity s-t Cut Problem (RobuCut), which has applications such as open-pit mining and project scheduling. In this paper, we show how RobuCut can be reduced to solving a sequence of maximum flow problems and provide an efficient algorithm for rapidly solving this sequence of problems. We demonstrate that our algorithm solves instances of RobuCut in seconds that would require hours if a standard maximum flow solver is iteratively used as a black-box subroutine. Copyright US Government 2011

Keywords: Maximum flows; Robust minimum cuts; Reoptimization heuristics; Goldberg-Tarjan algorithm; Robust network optimization; Incremental maximum flow algorithms (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0730-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:184:y:2011:i:1:p:3-26:10.1007/s10479-010-0730-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0730-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().