Fetching the paper…

Reading the bibliography…

2017

Simple Round Compression for Parallel Vertex Cover

Assadi, Sepehr

Original
PDF
Post on X

Understand

Recently, Czumaj et.al.

(arXiv 2017) presented a parallel (almost) $2$-approximation algorithm for the maximum matching problem in only $O({(\log\log{n})^2})$ rounds of the massive parallel computation (MPC) framework, when the memory per machine is $O(n)$.
The main approach in their work is a way of compressing $O(\log{n})$ rounds of a distributed algorithm for maximum matching into only $O({(\log\log{n})^2})$ MPC rounds.
In this note, we present a similar algorithm for the closely related problem of approximating the minimum vertex cover in the MPC framework.

Simple Round Compression for Parallel Vertex Cover · Around

Built on

Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
M. Parnas and D. Ron · 2007
Earlier work this paper cites.
A model of computation for mapreduce
H. J. Karloff, S. Suri, and S. Vassilvitskii · 2010
Earlier work this paper cites.
Maintaining a large matching and a small vertex cover
K. Onak and R. Rubinfeld · 2010
Earlier work this paper cites.
Sorting, searching, and simulation in the mapreduce framework
M. T. Goodrich, N. Sitchinava, and Q. Zhang · 2011
Earlier work this paper cites.

Similar

Filtering: a method for solving graph problems in mapreduce
S. Lattanzi, B. Moseley, S. Suri, and S. Vassilvitskii · 2011
Cited alongside, same era.
Communication steps for parallel query processing
P. Beame, P. Koutris, and D. Suciu · 2013
Cited alongside, same era.
Parallel algorithms for geometric graph problems
A. Andoni, A. Nikolov, K. Onak, and G. Yaroslavtsev · 2014
Cited alongside, same era.

Then

Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints
K. J. Ahn and S. Guha · 2015
Later among the works it cites.
Randomized composable coresets for matching and vertex cover
S. Assadi and S. Khanna · 2017
Closest in time.
Round compression for parallel matching algorithms
Original
A. Czumaj, J. Łącki, A. Mądry, S. Mitrović, K. Onak, and P. Sankowski · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…