论文标题
沟通有效的核心，以最大程度匹配
Communication Efficient Coresets for Maximum Matching
论文作者
论文摘要
在本文中，我们重新审视了构建以两分匹配的随机组合核的问题。在此问题中，输入图是在$ k $播放器上随机分区的，每个播放器将单个消息发送给协调器，然后在输入图中必须将良好的近似值输出到最大匹配。阿萨迪（Assadi）和卡纳（Khanna）给出了第一个这样的核心，通过让每个玩家发送最大匹配，即每位播放器最多$ n/2 $单词，从而获得了$ 1/9 $的核心。 Bernstein等人将近似因子提高到$ 1/3 $。 在本文中，我们表明Goel，Kapralov和Khanna的匹配骨架构造是一种精心选择的（分数）匹配，是一个随机的综合核心，可实现$ 1/2-O（1）$近似值的$ N-1 $ Communication。我们还显示了该核心达到的近似值的$ 2/3+O（1）$的上限。
In this paper we revisit the problem of constructing randomized composable coresets for bipartite matching. In this problem the input graph is randomly partitioned across $k$ players, each of which sends a single message to a coordinator, who then must output a good approximation to the maximum matching in the input graph. Assadi and Khanna gave the first such coreset, achieving a $1/9$-approximation by having every player send a maximum matching, i.e. at most $n/2$ words per player. The approximation factor was improved to $1/3$ by Bernstein et al. In this paper, we show that the matching skeleton construction of Goel, Kapralov and Khanna, which is a carefully chosen (fractional) matching, is a randomized composable coreset that achieves a $1/2-o(1)$ approximation using at most $n-1$ words of communication per player. We also show an upper bound of $2/3+o(1)$ on the approximation ratio achieved by this coreset.
