Talk on Clustering Perturbation Resilient Instances by Apoorv Vikram Singh

Date: 1st, December, 2018

Time: 5:00 pm

Venue: Room 134, Old Acad. Block, IIIT-Bangalore

Abstract:

Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world data sets that allow efficient clustering has lead to the notion of the perturbation resilience and center proximity. In the first part of the talk, we’ll see an algorithm to recover the optimal k-means clustering in perturbation resilient instances, and some lower bounds. In some cases, clustering with the k-means objective may result in a few clusters of very large cost and many clusters of small cost. This can be undesirable when we have a budget constraint on the cost of each cluster. Motivated by this, we study the “min-max k-means” clustering objective. In the second part of the talk, we’ll see approximation algorithms for the min-max k-means problem. This is a joint work with Dr. Amit Deshpande and Prof. Anand Louis.

About the Speaker:

Apoorv Vikram Singh graduated from IIIT Bangalore in 2018 and is a founding member of the Theory Club. He is currently working as a Project Associate in IISc., under the guidance of Prof. Anand Louis, and Dr. Amit Deshpande. Earlier, he worked on optimization methods for scheduling trains on a large railway network, tensor decomposition, and vehicle routing problems. He research broadly spans approximation algorithms, optimization and theoretical machine learning.

Link to the slides