Access to Data and Number of Iterations
Authors:
Open Access
- 13 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 4 (4) , 202-211
Abstract
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(n1+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(n1+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 round of MapReduce. The paper also proves that nonstandard linear relaxations of a problem, in particular penalty based formulations, are helpful in mapreduce and similar settings in reducing the adaptive dependence of the iterations.Keywords
Funding Information
- NSF CCF (1117216)
This publication has 28 references indexed in Scilit:
- A Local Computation Approximation Scheme to Maximum Matching2013
- Linear programming in the semi-streaming model with application to the maximum matching problemInformation and Computation, 2013
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2004
- Regret in the On-Line Decision ProblemGames and Economic Behavior, 1999
- A sublinear-time randomized approximation algorithm for matrix gamesOperations Research Letters, 1995
- The Weighted Majority AlgorithmInformation and Computation, 1994
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Convergence rate of the game processes for solving matrix gamesUSSR Computational Mathematics and Mathematical Physics, 1977