Minoux considered the maximum balanced flow problem of a two-terminal network, which is the problem of finding a maximum flow f in the network such that each arc-flow f(a) (a∈A) is bounded by a fixed proportion of the total flow value from the source to the sink, where A is the arc set of the network. He also proposed an algorithm for finding a maximum integral balanced flow, i.e., a maximum balanced flow satisfying that the value of each arc-flow of the network is integral. Integral balanced flows defined by Minoux can be regarded as one way to balance flows in the network. This paper, proposes another way to balance flows in a two-terminal network N. To be exact, it considers the maximum vertex-balanced flow problem in network N, i.e., the problem of finding a maximum flow f' in N such that for each vertex v∈V any arc-flow f'(a) (a∈δ’-(v)) entering v is bounded by a fixed proportion of the total flow ∈∈f'(a):a∈δ’-(v)∈ entering v, where V is the vertex set of N and δ’-(v) is the set of the arcs entering v. The intention was to propose an algorithm for finding a maximum integral vertex-balanced flow in network N, but it was found that the maximum integral vertex-balanced flow problem (IVBP) is difficult. The main purpose in this paper is to prove that problem (IVBP) is NP-complete and to propose a polynomial-time approximation algorithm for (IVBP).
