Algorithms for the Simple Equal Flow Problem
研究最小费用流的一个变种，要求指定弧集上的流量相等，称为简单等流量问题，源于意大利撒丁岛的水资源系统管理。提出了网络单纯形、参数单纯形、组合参数、二分搜索和容量缩放等算法，其中二分搜索可在O(log(nU))次最小费用流计算内求解，容量缩放算法的时间复杂度与最小费用流问题几乎相同。
The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set R ⊆ A of arcs and require that each arc in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all arc capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem—the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m + n logn) log (nU)) time, which is almost the same time needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem.