Please provide your feedback about the website at feedback@apc.iisc.ernet.in
Location: CSA Lecture Hall (Room No. 117, Ground Floor)
Department of Computer Science and Automation
Theory Seminar Series
Speaker : Mr. Karthik C.S
Postdoctoral fellow
Weizmann Institute of Science
Title : Inapproximability of Clustering in L_p metrics
Date : Friday, August 16, 2019
Time : 1:00 PM
Venue : CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract
The two most popular objectives optimized in clustering algorithms are k-means and k-median. The k-means (resp. k-median) problem in the L_p-metric is specified by n points as input and the goal is to classify the input point-set into k clusters such that the k-means (resp. k-median) objective is minimized. The best-known inapproximability factor in literature for these NP-hard problems in L_p-metrics were well-below 1.01. In this talk, we take a significant step to improve the hardness of approximating these problems in various L_p-metrics. Our techniques are inspired by the tools and perspectives developed in fine-grained complexity in the last couple of years. The talk is based on a joint work with Vincent Cohen-Addad.
Biography of the speaker
Karthik C.S. is a postdoctoral fellow in Weizmann Institute of Science. He is interested in Hardness of Approximation in Fine-Grained and Fixed-Parameter Complexity, Probabilistically Checkable Proofs, and Communication Complexity. He received his PhD from Weizmann Institute of Science and Master’s from École Normale Supérieure de Lyon.
Host Faculty : Dr. Arindam Khan
