Improved balanced flow computation using parametric flow

• Balanced flows are an important ingredient in market equilibrium computations.
• An improved algorithm for computing balanced flows in equality networks is presented.
• The algorithm is an application of parametric flows.
• The algorithm improves the running time of some market equilibrium algorithms.

We present a new algorithm for computing balanced flows in equality networks arising in market equilibrium computations. The current best time bound for computing balanced flows in such networks requires O(n)O(n) maxflow computations, where n is the number of nodes in the network [1]. Our algorithm requires only a single parametric flow computation. The best algorithm for computing parametric flows [3] is only by a logarithmic factor slower than the best algorithms for computing maxflows. Hence, the running time of the algorithms in Devanur et al. [1] and Duan and Mehlhorn [2] for computing market equilibria in linear Fisher and Arrow–Debreu markets improve by almost a factor of n.