BARC talk by Shyam Narayanan

Wednesday, 13 July 2022, Shyam Narayanan, PhD student at Massachusetts Institute of Technology, USA, will give a talk on "Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets".

Title: 
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets

Abstract: 
Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean k-median and k-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of 2.406 and 5.912 for Euclidean k-median and k-means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat. Our techniques involve a much stronger exploitation of the Euclidean metric than previous work on Euclidean clustering. In addition, we introduce a new method of removing excess centers using a variant of independent sets over graphs that we dub a "nested quasi-independent set". In turn, this technique may be of interest for other optimization problems in Euclidean and ℓp metric spaces.

Bio: 
Shyam Narayanan is a 3rd year Ph.D. student at the Massachusetts Institute of Technology, advised by Prof. Piotr Indyk. Before that, he was an undergraduate student at Harvard University. He is interested in a wide range of algorithmic problems, and much of his research has been on clustering algorithms or algorithmic statistics problems. He is also interested in differential privacy, streaming algorithms, learning-augmented algorithms, and combinatorics.