BARC talk by Shyam Narayanan
Summary
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. 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.