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 consider graph algorithms in models of computation where thespace usage (random accessible storage, in addition to the read only input) issublinear in the number of edges $m$ and the access to input data isconstrained. These questions arises in many natural settings, and in particularin the analysis of MapReduce or similar algorithms that model constrainedparallelism with sublinear central processing. In SPAA 2011, Lattanzi etal.provided a $O(1)$ approximation of maximum matching using $O(p)$ rounds ofiterative filtering via mapreduce and $O(n^{1+1/p})$ space of centralprocessing for a graph with $n$ nodes and $m$ edges.  We focus on weighted nonbipartite maximum matching in this paper. For anyconstant $p>1$, we provide an iterative sampling based algorithm for computinga $(1-\epsilon)$-approximation of the weighted nonbipartite maximum matchingthat uses $O(p/\epsilon)$ rounds of sampling, and $O(n^{1+1/p})$ space. Theresults extends to $b$-Matching with small changes. This paper combinesadaptive sketching literature and fast primal-dual algorithms based on relaxedDantzig-Wolfe decision procedures. Each round of sampling is implementedthrough linear sketches and executed in a single round of MapReduce. The paperalso proves that nonstandard linear relaxations of a problem, in particularpenalty based formulations, are helpful in mapreduce and similar settings inreducing the adaptive dependence of the iterations.

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints