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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present a deterministic $(1+\varepsilon)$-approximate maximum matchingalgorithm in $\mathsf{poly} 1/\varepsilon$ passes in the semi-streaming model,solving the long-standing open problem of breaking the exponential barrier inthe dependence on $1/\varepsilon$. Our algorithm exponentially improves on thewell-known randomized $(1/\varepsilon)^{O(1/\varepsilon)}$-pass algorithm fromthe seminal work by McGregor~[APPROX05], the recent deterministic algorithm byTirodkar with the same pass complexity~[FSTTCS18]. Up to polynomial factors in$1/\varepsilon$, our work matches the state-of-the-art deterministic $(\log n /\log \log n) \cdot (1/\varepsilon)$-pass algorithm by Ahn and Guha~[TOPC18],that is allowed a dependence on the number of nodes $n$. Our result also makesprogress on the Open Problem 60 at sublinear.info.  Moreover, we design a general framework that simulates our approach for thestreaming setting in other models of computation. This framework requiresaccess to an algorithm computing an $O(1)$-approximate maximum matching and analgorithm for processing disjoint $(\mathsf{poly} 1 / \varepsilon)$-sizeconnected components. Instantiating our framework in $\mathsf{CONGEST}$ yieldsa $\mathsf{poly}(\log{n}, 1/\varepsilon)$ round algorithm for computing$(1+\varepsilon$)-approximate maximum matching. In terms of the dependence on$1/\varepsilon$, this result improves exponentially state-of-the-art result byLotker, Patt-Shamir, and Pettie~[LPSP15]. Our framework leads to the samequality of improvement in the context of the Massively Parallel Computationmodel as well.

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond