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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the communication complexity and streaming complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G=(A, B, E), with n=|A|, is a subset of edges S⊆E that matches all A vertices to B vertices with the goal usually being to do this as fairly as possible. While the term semi-matching was coined in 2003 by Harvey et al. [WADS 2003], the problem had already previously been studied in the scheduling literature under different names. We present a deterministic one-pass streaming algorithm that for any 0≤ε≤1 uses space Õ(n1+ε) and computes an O(n(1−ε)/2)-approximation to the semi-matching problem. Furthermore, with o(logn) passes it is possible to compute an O(logn)-approximation with space Õ(n). In the one-way two-party communication setting, we show that for every ε0, deterministic communication protocols for computing an O$(n^{\frac{1}{(1+\epsilon)c + 1}})$-approximation require a message of size more than cn bits. We present two deterministic protocols communicating n and 2n edges that compute an O$(\sqrt{n})$ and an O(n1/3)-approximation respectively. Finally, we improve on results of Harvey et al. [Journal of Algorithms 2006] and prove new links between semi-matchings and matchings. While it was known that an optimal semi-matching contains a maximum matching, we show that there is a hierachical decomposition of an optimal semi-matching into maximum matchings. A similar result holds for semi-matchings that do not admit length-two degree-minimizing paths.

Approximating Semi-matchings in Streaming and in Two-Party Communication