We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al.
%0 Conference Paper
%1 DBLP:conf/stoc/Orlin10
%A Orlin, James B.
%B STOC
%D 2010
%K fisher market
%P 291-300
%R 10.1145/1806689.1806731
%T Improved algorithms for computing fisher's market clearing prices
%X We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al.
@inproceedings{DBLP:conf/stoc/Orlin10,
abstract = {We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al.},
added-at = {2010-11-06T00:48:55.000+0100},
author = {Orlin, James B.},
bibsource = {DBLP, http://dblp.uni-trier.de},
biburl = {https://www.bibsonomy.org/bibtex/2ca206dc13f55ae26ff4377b75193e889/ytyoun},
booktitle = {STOC},
crossref = {DBLP:conf/stoc/2010},
doi = {10.1145/1806689.1806731},
interhash = {eb09c84996a0a5c6d039fcb3195989fc},
intrahash = {ca206dc13f55ae26ff4377b75193e889},
keywords = {fisher market},
pages = {291-300},
timestamp = {2011-10-01T06:50:48.000+0200},
title = {Improved algorithms for computing fisher's market clearing prices},
year = 2010
}