Abstract Consider the following communication problem. Alice holds a graph and Bob holds a graph , where |P|=|Q|=n. Alice is allowed to send Bob a message m that depends only on the graph GA. Bob must then output a matching . What is the minimum message size of the message m that Alice sends to Bob that allows Bob to recover a matching of size at least times the maximum matching in ? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a 1/2-approximation was known for both these problems.
We show that for any , a -approximation requires a communication complexity of .
We also consider the natural restrictingon of the problem in which and are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a 3/4-approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation.
Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1-1/e)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming (1-1/e)-approximation algorithm using O(n) space for this setting.
Guest: Michael Kaparalov
Host: Yvonne-Anne Pignolet