A strongly polynomial algorithm for the Balanced network flow problem

We show that the Balanced Network Flow Problem in the case of general weights, i.e., the problem of finding a feasible flow on a given network which minimizes the difference between the maximum and the minimum weighted flow on single arcs, can be solved in strongly polynomial time. The proposed solution algorithm consists of extending Megiddo's approach for parametric programming.