Title: Randomized Composable Coresets for Matching and Vertex Cover,
Abstract: A common approach for designing scalable algorithms for massive data sets is
to distribute the computation across, say $k$, machines and process the data
using limited communication between them. A particularly appealing framework
here is the simultaneous communication model whereby each machine constructs a
small representative summary of its own data and one obtains an
approximate/exact solution from the union of the representative summaries. If
the representative summaries needed for a problem are small, then this results
in a communication-efficient and round-optimal protocol. While many fundamental
graph problems admit efficient solutions in this model, two prominent problems
are notably absent from the list of successes, namely, the maximum matching
problem and the minimum vertex cover problem. Indeed, it was shown recently
that for both these problems, even achieving a polylog$(n)$ approximation
requires essentially sending the entire input graph from each machine.
The main insight of our work is that the intractability of matching and
vertex cover in the simultaneous communication model is inherently connected to
an adversarial partitioning of the underlying graph across machines. We show
that when the underlying graph is randomly partitioned across machines, both
these problems admit randomized composable coresets of size $\widetilde{O}(n)$
that yield an $\widetilde{O}(1)$-approximate solution. This results in an
$\widetilde{O}(1)$-approximation simultaneous protocol for these problems with
$\widetilde{O}(nk)$ total communication when the input is randomly partitioned
across $k$ machines. We further prove the optimality of our results. Finally,
by a standard application of composable coresets, our results also imply
MapReduce algorithms with the same approximation guarantee in one or two rounds
of communication