A strongly polynomial algorithm for the uniform balanced network flow problem Original Research Article

Several balanced optimization problems have been analysed in the literature. Here, the balanced network flow problem in the uniform case is studied, and it is shown that it can be solved by the Newtonʹs approach inO(n2 log3 n) max-flow computations. The key of the proof is an extension of Radzikʹs analysis of Newtonʹs method for linear fractional combinatorial optimization problems.