Communication Efficient Coresets for Maximum Matching
Michael Kapralov, Gilbert Maystre, Jakab Tardos · Society for Industrial and Applied Mathematics eBooks · 2021
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 [6] 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. [2]. In this paper, we show that the matching skeleton construction of Goel, Kapralov and Khanna [20], 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.