Minimax inverse problems of minimum cuts
Let G = (N, A) be a directed graph of n nodes and m arcs with an upper bound u is an element of Z(A). Given an s-t cut S-0, the minimax inverse minimum-cut problem (MIMC) is to find a modified upper bound (u) over tilde is an element of R-A such that S-0 is a minimum cut for (u) over tilde and max {\ uij - (u) over tilde ij parallel to (i, j) is an element of A} is minimum. This paper shows that the MIMC is closely related to the maximum mean-cut problem. By applying a parametric search for maximum mean-cut problems, the MIMC can be solved as a sequence of O(n) minimum s-t cut problems or in O(min {n(2/3), m(1/2)}m log (n(2)/m) log n log (nU)) time, where U is the maximum value of u. (C) 2002 John Wiley Sons, Inc.
minimum-cut problem parametric search inverse optimization maximum mean cut