NP-COMPLETENESS AND APPROXIMATION ALGORITHM FOR THE MAXIMUM INTEGRAL VERTEX-BALANCED FLOW PROBLEM

概要

論文の詳細を見る
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. In this paper, we propose another way to balance flows in a two-terminal network N. To be exact, we consider 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. We intended to propose an algorithm for finding a maximum integral vertex-balanced flow in network N, but we found that the maximum integral vertex-balanced flow problem (IVBP) is difficult. Our main purpose in this paper is to prove that problem (IVBP) is NP-complete and to propose a polynomial-time approximation algorithm for (IVBP).
社団法人日本オペレーションズ・リサーチ学会の論文