A Massively Parallel Algorithm for Minimum Weight Vertex Cover

Mohsen Ghaffari, Ce Jin, Daan Nilis

We present a massively parallel algorithm, with near-linear memory per machine, that computes a $(2+\epsilon )$-approximation of minimum-weight vertex cover in $O(\log \log d)$ ro…