Improved balanced flow computation using parametric flow

DOI10.1016/J.IPL.2016.04.008MaRDI QIDQ284342zbMATH OpenOpenAlexFDO

Authors Omar Darwish, K. Mehlhorn

Publication date 18 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.05974

zbMATH Keywords

algorithmsnetwork flowmarket equilibriumbalanced flowparametric flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Special types of economic equilibria (91B52)

Abstract: 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)$ maxflow computations, where $n$ is the number of nodes in the network [Devanur et al. 2008]. Our algorithm requires only a single parametric flow computation. The best algorithm for computing parametric flows [Gallo et al. 1989] 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. 2008] and [Duan and Mehlhorn 2015] for computing market equilibria in linear Fisher and Arrow-Debreu markets improve by almost a factor of $n$.

Recommendations

• A note on balanced flows in equality networks
• Balancing Applied to Maximum Network Flow Problems
• Concave generalized flows with applications to market equilibria
• Improved algorithms for computing Fisher's market clearing prices
• Auction Algorithms for Market Equilibrium

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• A Faster Deterministic Maximum Flow Algorithm
• A Randomized Maximum-Flow Algorithm
• A new approach to the maximum-flow problem
• An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market
• Existence of an Equilibrium for a Competitive Economy
• Market equilibrium via a primal-dual algorithm for a convex program
• Max flows in \(O(nm)\) time, or better

Cited in

(5)

• Improved iteration scheme for partial equilibrium flow
• A note on balanced flows in equality networks
• Ratio-balanced maximum flows
• Combinatorial algorithms for general linear Arrow-Debreu markets
• Parametric computation of equilibria and flows

This page was built for publication: Improved balanced flow computation using parametric flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284342)