<![CDATA[MoneyScience: Quantitative Finance at arXiv's blog: Concave Generalized Flows with Applications to Market Equilibria. (arXiv:1109.3893v2 [cs.DS] UPDATED)]]>
https://www.moneyscience.com/pg/blog/arXiv/read/164430/concave-generalized-flows-with-applications-to-market-equilibria-arxiv11093893v2-csds-updated?view=rss
https://www.moneyscience.com/pg/blog/arXiv/read/164430/concave-generalized-flows-with-applications-to-market-equilibria-arxiv11093893v2-csds-updatedWed, 02 Nov 2011 19:30:47 -0500
https://www.moneyscience.com/pg/blog/arXiv/read/164430/concave-generalized-flows-with-applications-to-market-equilibria-arxiv11093893v2-csds-updated
<![CDATA[Concave Generalized Flows with Applications to Market Equilibria. (arXiv:1109.3893v2 [cs.DS] UPDATED)]]>We consider a nonlinear extension of the generalized network flow model, with
the flow leaving an arc being an increasing concave function of the flow
entering it, as proposed by Truemper and Shigeno. We give the first polynomial
time combinatorial algorithm for solving corresponding flow maximization
problems, finding an epsilon-approximate solution in O(m(m+\log
n)\log(MUm/epsilon)) arithmetic operations and value oracle queries, where M
and U are upper bounds on simple parameters. For (linear) generalized flows,
our algorithm can be seen as an extension of the highest-gain augmenting path
algorithm by Goldfarb, Jin and Orlin.
read more...