Hardness of Approximation of Diameter Clustering by Karthik C. S. (Rutgers University)

Date : 20 Nov 2023
Abstract:
In the k-Diameter Clustering problem, we are given as input a set of points in a metric space, and the goal is to partition the pointset to k parts so as to minimize the maximum diameter across the parts. In the 1980s, a 2 factor polynomial time approximation algorithm was proposed for this problem (in all metrics). On the other hand, it was shown that approximating the k-Diameter problem to a factor better than 2 in the L-1 and L-infinity metrics, and to a factor better than 1.97 in the Euclidean metric is NP-hard. However, all the known hardness results were for the case when k (the number of clusters) was linear in the input size. In this talk, I will present some exciting new results on the (in)-approximability of the k-Diameter problem when k is a constant (for example k=3).

Joint work with Henry Fleischmann (University of Cambridge), Kyrylo Karlov (Charles University), Ashwin Padaki (Columbia University), and Styopa Zharkov (Stanford University).

Talk Link:

[ad_2]

source