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

本研究证明，匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区，进而展示这两个问题存在随机组分的可组合核的对数 O (n)。