Near-Optimal Clustering on Massive Graphs

When: Thursday, July 25, 2019 (CANCELLED)
Where: PGH 563
Time: 11:00 AM

Speaker: Dr. Sriram V. Pemmaraju, University of Iowa

Host: Dr. Gopal Pandurangan, University of Houston

The clustering problem, in its many variants, has numerous applications in operations research and computer science. As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in systems suited for large-scale computation such Apache Spark and Giraph. The k-machine model and the MPC model are simple, message-passing models for large-scale distributed and parallel computing. This talk considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the p-median problem, and the p-center problem and presents efficient O(1)-factor approximation algorithms for these problems running in the k-machine and MPC models. The talk will also consider outlier versions of these problems. Time permitting, we will end with a discussion of the optimality of these algorithms.

Bio:

Sriram Pemmaraju is a professor in computer science at the University of Iowa and the director of graduate studies there. His research is on theoretical aspects of distributed algorithms, especially the role of randomization in the design of these algorithms and the use of communication complexity and information-theoretic techniques to prove distributed computing lower bounds. His research is supported by the National Science Foundation and National Institutes of Health and it has received several best paper awards. He has mentored 11 PhD students and has received several outstanding graduate mentor nominations.