Abstract: In this talk, I will present three recent algorithms for different versions of the bipartite matching problem along with exciting on-going and future research directions.

 

First, I will present a new algorithm for the maximum cardinality matching problem for bipartite graphs with small vertex separators. The classical Hopcroft-Karp algorithm [SICOMP 1973] and the divide and conquer algorithm by Lipton and Tarjan [SICOMP 1980] solve this problem in O(n^1.5 ) time. Our algorithm combines the two approaches resulting in an improved execution time of O(n^1.33 ). This algorithm can be used to compute a bottleneck distance and Levy-Prokhorov distance between low dimensional point sets.

 

Next, I will present a new algorithm for the minimum-cost bipartite matching problem between two sets of n samples each drawn i.i.d from an unknown two-dimensional distribution. Despite decades of effort, an efficient implementation of the classical Hungarian method that runs in near-quadratic time remains the best-known exact algorithm for this problem. I will present a novel adaptation of the Hungarian algorithm in the geometric divide-and-conquer framework that computes the exact solution in O(n^1.75 ). Our algorithm extends to any fixed dimensional space and is helpful in computing the optimal transport distances that is extensively used in machine learning (training GANs) and statistical inference (the two-sample test).

 

Finally, I present a novel online algorithm for minimum-cost matching in metric spaces. Here, requests arrive in an online fashion, and we must irrevocably assign a server to serve the request. I present a robust online algorithm that achieves a near-optimal competitive ratio across different request generation models and across different metric spaces thus making substantial progress on a long-standing open problem in online algorithms.

Short Bio: Sharath Raghvendra is an Associate Professor in the Department of Computer Science at Virginia Tech. Before joining Virginia Tech, he spent two years (2012-2014) as a postdoctoral scholar at Stanford University. Dr. Raghvendra received his Ph.D. from Duke University in 2012 where he won the Best Doctoral Dissertation Award. His research interests focus on designing provable algorithms for optimization including problems related to matching and optimal transport amongst other areas. His work has been published in top-tier conferences and journals in theoretical computer science and machine learning, such as the Journal of the ACM, ACM SIAM Symposium on Discrete Algorithms (SODA), International Symposium on Computational Geometry (SoCG), ACM Symposium on Theory of Computing (STOC), IEEE Symposium on Foundations of Computer Science (FOCS), Advances in Neural Information Processing Systems (NeurIPS) and International Conference on Learning Representation (ICLR). His research is supported by multiple grants from the National Science Foundation.