|
CS seminar announcement Date/Time: Monday, March 6, 2023. 14.00. Venue: Lecture Hall 6, Chennai Mathematical Institute A Tour of Clustering and Geometric Problems Tanmay Inamdar University of Bergen, Norway. 06-03-23 Abstract Clustering is a widely used unsupervised learning technique that groups "similar" objects together. It has been shown that even a small number of outliers can influence the results of clustering algorithms, obscuring the natural underlying clusters. Thus, the study of clustering in the presence of outliers is vital for practical applications. In a "clustering with outliers" problem, we are given a set of points P and two parameters k and m, and the clustering should partition P into k clusters, excluding up to m outlier points. In this talk, I will present a general framework to reduce a "clustering with outliers" problem to its outlier-free analogue, at the expense of a small loss in the approximation guarantee (our recent result [1], AAAI '23). This reduction allows us to obtain optimal FPT-approximation algorithms for a number of clustering problems, such as k-median/k-means with outliers. I will also briefly discuss some of my other results related to clustering and geometric optimization problems, and interesting future directions related to these areas. [1] Clustering What Matters: Optimal Approximations for Clustering with Outliers. Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue. AAAI 2023 (Distinguished Paper) https://arxiv.org/abs/2212.00696 Abount the Speaker: Tanmay Inamdar is a Researcher at University of Bergen, Norway. He received PhD in Computer Science in 2020 from the University of Iowa, USA. His research interests lie in Theoretical Computer Science, particularly in the areas of Approximation and Parameterized Algorithms, and Computational Geometry.
|
