Title: Approximating Matching Size from Random Streams
Speaker: Michael Kapralov, IBM Watson
Date: Wednesday, December 10, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore $\tilde{O}(\sqrt{n})$ approximation with polylogarithmic space in an $n$ vertex graph and a constant approximation with $\Omega(n)$ space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in $n$.
Our algorithm is obtained by effecting a streaming implementation of a simple "local" algorithm that we design for this problem. The local algorithm produces a $O(k\cdot n^{1/k})$ approximation to the size of a maximum matching by exploring the radius $k$ neighborhoods of vertices, for any parameter $k$. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for $k = \Omega(\log n/\log\log n)$. Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.
This is joint work with Sanjeev Khanna and Madhu Sudan.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/