A Strongly Polynomial Algorithm for Generalized Flow Maximization
该文提出一种称为连续缩放的新缩放技术，为广义流最大化问题设计了强多项式算法，能在强多项式步数内识别必须紧的弧并收缩，进而也得到约束矩阵每列至多两个非零元的线性可行性问题的强多项式算法。
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.