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

Christian Konrad, Adi Rosén

Research output: Contribution to journalArticle (Academic Journal)peer-review

140 Downloads (Pure)

Abstract

We study the streaming complexity and communication 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. [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(log n) passes it is possible to compute an O(log n)-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(n1/(1+ε)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 the results of Harvey et al. [2003] 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 hierarchical 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.
Original languageEnglish
Article number32
Number of pages32
JournalACM Transactions on Algorithms
Volume12
Issue number3
Early online date15 Jun 2016
DOIs
Publication statusPublished - 2016

Fingerprint

Dive into the research topics of 'Approximating Semi-matchings in Streaming and in Two-Party Communication'. Together they form a unique fingerprint.

Cite this