With the rapid advances in technology, real-world data sets have embraced an ever-expanding complexity that the traditional algorithms cannot address. One challenge is the massive size of these data sets which demands highly resource efficient algorithms. This has resulted in a growing interest in designing streaming and massiv
In this thesis, we propose and analyze algorithms for fundamental graph problems such as maximum matching, minimum spanning tree, minimum bisection, and graph clustering methods (such as single-linkage and its variants) in the aforementioned models. These algorithms improve over the state-of-the-art via the tools, techniques, and most importantly, combinatorial observations that we demonstrate throughout this thesis. Although our main focus is on the theoretical guarantees of the proposed algorithms, they are also arguably simple and practical. We exhibit this via experiments on real-world graphs and internal data sets of giant tech companies such as Google.
Dept. rep: Dr. John Dickerson
Members: Dr. Aravind Srinivasan
Dr. Vahab Mirrokni