A POLYNOMIAL-TIME BINARY SEARCH ALGORITHM FOR THE MAXIMUM BALANCED FLOW PROBLEM

概要

論文の詳細を見る
We consider the maximum balanced flow problem of a two-terminal network N, i.e.,a maximum flow problem with an additional constraint described in terms of a balancing rate function α : A → R_+ - {0}, where A is the arc set of N and R_+ is the set of nonnegative reals. In this paper, we propose a polynomial time algorithm for the maximum balanced flow problem, on condition that all given functions in N are rational. The proposed algorithm, which is composed of a binary search algorithm and Dinic's maximum flow algorithm with a parameter, requires O(max{log(c*), mlog(η*), nm}T(n, m)) time, where c* = max{c^o(a) : a ∈ A} for positive integral arc-capacities (c^o(a) : a ∈ A) and η* = max{η(a) : a ∈ A} for α(a) ≡ ζ(a)/η(a) ≤ 1 such that ζ (a) and η(a) are positive integers, and T(n, m) is the time for the maximum flow computation for a network with n vertices and m = |A| arcs.
社団法人日本オペレーションズ・リサーチ学会の論文