Seminars

View all Seminars  |  Download ICal for this event

Hardness of Approximation of Diameter Clustering

Series: Bangalore Theory Seminars

Speaker: Karthik C. S., Rutgers University

Date/Time: Nov 20 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

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).

Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series

Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas