English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we present an $\tilde{O}(m\sqrt{n}\log^{O(1)}U)$ time algorithmfor solving the maximum flow problem on directed graphs with $m$ edges, $n$vertices, and capacity ratio $U$. This improves upon the previous fastestrunning time of$O(m\min\left(n^{2/3},m^{1/2}\right)\log\left(n^{2}/m\right)\log U)$ achievedover 15 years ago by Goldberg and Rao. In the special case of solving densedirected unit capacity graphs our algorithm improves upon the previous fastestrunning times of of $O(\min\{m^{3/2},mn^{^{2/3}}\})$ achieved by Even andTarjan and Karzanov over 35 years ago and of $\tilde{O}(m^{10/7})$ achievedrecently by M\k{a}dry.  We achieve these results through the development and application of a newgeneral interior point method that we believe is of independent interest. Thenumber of iterations required by this algorithm is better than that predictedby analyzing the best self-concordant barrier of the feasible region. Byapplying this method to the linear programming formulations of maximum flow,minimum cost flow, and lossy generalized minimum cost flow and applyinganalysis by Daitch and Spielman we achieve running time of$\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ for these problems as well.Furthermore, our algorithm is parallelizable and using a recent nearly lineartime work polylogarithmic depth Laplacian system solver of Spielman and Peng weachieve a $\tilde{O}(\sqrt{n}\log^{O(1)}(U/\epsilon))$ depth algorithm and$\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ work algorithm for solving theseproblems.

Path Finding II : An \~O(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem