We present a new scaling algorithm for the maximum mean cut problem. T
he mean of a cut is defined by the cut capacity divided by the number
of area crossing the cut. The algorithm uses an approximate binary sea
rch and solves the circulation feasibility problem with relaxed capaci
ty bounds. The maximum mean cut problem has recently been studied as a
dual analogue of the minimum mean cycle problem in the framework of t
he minimum cost flow problem by Ervolina and McCormick. A network N =
(G, lower, upper) with lower and upper are capacities is said to be de
lta-feasible if N has a feasible circulation when we relax the capacit
y bounds by delta; that is, we use (lower(a) - delta, upper(a) + delta
) bounds instead of(lower(a), upper(a)) bounds for each are a is an el
ement of A. During an approximate binary search we maintain two bounds
, LB and UB, such that N is LB-infeasible and UB-feasible, and we redu
ce the interval size (LB, UB) by at least one-third at each iteration.
For a graph with n vertices, m arcs, and integer capacities bounded b
y U, the running time of this algorithm is O(mn log(nU)). This time bo
und is better than the time achieved by McCormick and Ervolina under t
he similarity condition (that is, U = O(nO(0(1)))). Our algorithm can
be naturally used for the circulation feasibility problem, and thus pr
ovides a new scaling algorithm for the minimum cut problem.