Communication Efficient Coresets for Maximum Matching

11/12/2020
by   Michael Kapralov, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset