Abstract
While there has been significant strides made in developing small space algorithms in many constrained settings generally referred to massive data algorithms, a natural and ever present question remains: Can these techniques focused on constrained representations allow us to solve problems which we did not know how to solve in an unconstrained setting earlier?
In this talk we investigate classic variants of the Maximum Matching problem. We show that using ideas from succinct representations and linear programming, we can provide near optimal approximation schemed for several variants in near linear time which we did not know before. These ideas also improve the number of passes required by popular algorithmic frameworks such as MapReduce or Semi-Streaming for computing near optimal solutions to the maximum matching problem (as well as variants).