Approximation Algorithms for Continuous Clustering and Facility Location Problems
Abstract: I will talk about clustering and facility location in metric spaces -- for example, the k-median and k-means problems in a metric space. I will describe approximation algorithms for the continuous case of such problems, where the cluster centers can be chosen from anywhere in the potentially infinite-sized ambient metric space. The motivation behind this work is to compare the approximability of the continuous case with that of the discrete case -- in the latter, the cluster centers must themselves be input points.
It is known, via the triangle inequality, that if we have an alpha-approximation for the discrete case, then we also have a beta*alpha-approximation for the continuous case, where beta depends on the specific problem; this beta is 2 for k-median and 4 for k-means. This work asks whether this beta gap is "tight", i.e. can we do better for the continuous case than simply reducing to the discrete case and suffering a beta-factor blowup?
I will present positive results for k-means and a few related problems; that is, I will describe algorithms for the continuous case of these problems that beat beta times the best known approximation ratio for the discrete case. For k-median, the motivating question remains open. The positive results are via a new linear program, and the use of the round-or-cut method with this linear program.
This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.
Bio: Ankita Sarkar is a Ph.D. student in Theoretical Computer Science at Dartmouth College, advised by Prof. Deeparnab Chakrabarty. Her current research focuses on designing approximation algorithms for clustering and covering problems. Her broader interests include online algorithms and graph algorithms. Before Dartmouth, Ankita studied mathematics and computer science at Chennai Mathematical Institute, India.