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

We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximumcardinality bipartite matching and related problems (e.g. transshipment,negative-weight shortest paths, and optimal transport) on $m$-edge, $n$-nodegraphs. For maximum cardinality bipartite matching on moderately dense graphs,i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in theinput size and constitutes the first improvement over the classic$O(m\sqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\tildeO(n^\omega)$-time algorithms [Ibarra-Moran 1981; Mucha-Sankowski 2004] (wherecurrently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 +\delta}$ for any constant $\delta>0$, our result improves upon the recentadvances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an$\tilde O(m^{4/3+o(1)})$ runtime.  We obtain these results by combining and advancing recent lines of researchin interior point methods (IPMs) and dynamic graph algorithms. First, wesimplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing ageneral primal-dual IPM framework and new sampling-based techniques forhandling infeasibility induced by approximate linear system solvers. Second, weprovide a simple sublinear-time algorithm for detecting and samplinghigh-energy edges in electric flows on expanders and show that when combinedwith recent advances in dynamic expander decompositions, this yields efficientdata structures for maintaining the iterates of both [v.d.Brand et al.] and ournew IPMs. Combining this general machinery yields a simpler $\tilde O(n\sqrt{m})$ time algorithm for matching based on the logarithmic barrierfunction, and our state-of-the-art $\tilde O(m+n^{1.5})$ time algorithm formatching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brandet al.]).

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs