Inapproximability of Clustering in L_p metrics by Mr. Karthik C.S, Weizmann Institute of Science

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)


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

Scroll Up