Inapproximability of Clustering in L_p metrics (Karthik C. S)


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 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. In particular, there is an interesting interplay between geometric embeddings and communication protocols that will be emphasized and exploited in our proofs.


2019-06-04   14:00 ~ 15:00   


Karthik C. S, Weizmann Institute of Science


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics