@inproceedings{7251082319c4471ebd0389dac2639d80,

title = "An improved combinatorial polynomial algorithm for the linear arrow-debreu market",

abstract = "We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear ArrowDebreu model. For a market with n agents and integral utilities bounded by U, the algorithm runs in O(n7 log3(nU)) time. This improves upon the previously best algorithm of Ye by a factor of Ω(n). The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of Ω(n3). The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.",

author = "Ran Duan and Jugal Garg and Kurt Mehlhorn",

year = "2016",

doi = "10.1137/1.9781611974331.ch7",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "90--106",

editor = "Robert Krauthgamer",

booktitle = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016",

address = "United States",

note = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 ; Conference date: 10-01-2016 Through 12-01-2016",

}