English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper we revisit the problem of constructing randomized composablecoresets for bipartite matching. In this problem the input graph is randomlypartitioned across $k$ players, each of which sends a single message to acoordinator, who then must output a good approximation to the maximum matchingin 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. atmost $n/2$ words per player. The approximation factor was improved to $1/3$ byBernstein 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 arandomized composable coreset that achieves a $1/2-o(1)$ approximation using atmost $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.

Communication Efficient Coresets for Maximum Matching