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

Christian Konrad, Adi Rosén

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 su…