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

As massive graphs become more prevalent, there is a rapidly growing need forscalable algorithms that solve classical graph problems, such as maximummatching and minimum vertex cover, on large datasets. For massive inputs,several different computational models have been introduced, including thestreaming model, the distributed communication model, and the massivelyparallel computation (MPC) model that is a common abstraction ofMapReduce-style computation. In each model, algorithms are analyzed in terms ofresources such as space used or rounds of communication needed, in addition tothe more traditional approximation ratio.  In this paper, we give a single unified approach that yields betterapproximation algorithms for matching and vertex cover in all these models. Thehighlights include:  * The first one pass, significantly-better-than-2-approximation for matchingin random arrival streams that uses subquadratic space, namely a$(1.5+\epsilon)$-approximation streaming algorithm that uses $O(n^{1.5})$ spacefor constant $\epsilon > 0$.  * The first 2-round, better-than-2-approximation for matching in the MPCmodel that uses subquadratic space per machine, namely a$(1.5+\epsilon)$-approximation algorithm with $O(\sqrt{mn} + n)$ memory permachine for constant $\epsilon > 0$.  By building on our unified approach, we further develop parallel algorithmsin the MPC model that give a $(1 + \epsilon)$-approximation to matching and an$O(1)$-approximation to vertex cover in only $O(\log\log{n})$ MPC rounds and$O(n/poly\log{(n)})$ memory per machine. These results settle multiple openquestions posed in the recent paper of Czumaj~et.al. [STOC 2018].

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs