Improved balanced flow computation using parametric flow

DOI10.1016/J.IPL.2016.04.008zbMATH Open1361.91050arXiv1512.05974OpenAlexW2221924776MaRDI QIDQ284342FDOQ284342

Omar Darwish, K. Mehlhorn

Publication date: 18 May 2016

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

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$.

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

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

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)

Cites Work

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

Cited In (4)

• Ratio-balanced maximum flows
• A note on balanced flows in equality networks
• Title not available (Why is that?)
• Improved iteration scheme for partial equilibrium flow

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)