Can I read Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints on EtoBox?

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints by Kook Jin Ahn; Sudipto Guha is a scholarly article available to read on EtoBox.

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

In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number of edges m and the access to input data is constrained. These questions arises in many natural settings, and in particular in the analysis of MapReduce or similar algorithms that model constrained parallelism with sublinear central processing. In SPAA 2011, Lattanzi etal. provided a O(1) approximation of maximum matching using O(p) rounds of iterative filtering via mapreduce and O(n 1+1/p ) space of central processing for a graph with n nodes and m edges. We focus on weighted nonbipartite maximum matching in this paper. For any constant p > 1, we provide an iterative sampling based algorithm for computing a (1 -)approximation of the weighted nonbipartite maximum matching that uses O(p/ ) rounds of sampling, and O(n 1+1/p ) space. The results extends to b-Matching with small changes. This paper combines adaptive sketching literature and fast primal-dual algorithms based on relaxed Dantzig-Wolfe decision procedures. Each round of sampling is implemented through linear sketches and executed in a single roun

Author

Kook Jin Ahn; Sudipto Guha

Publisher

ACM

Published

2015

Language

EN