Lecture Announcement
Date: 13th Dec, 2022. Time: 3:30 pm.
Venue: LH 5.
Approximation algorithms for continuous clustering and facility location problems
Ankita Sarkar
Dortmund Univ.
13-12-22

---

Abstract

I will talk about approximation algorithms for the metric k-median, metric k-means, and related problems. I will address the continuous version of these problems, where the cluster centers can be chosen from anywhere in the potentially infinite-sized ambient metric space; and I will compare with the discrete version, where the cluster centers must be from among the input points. It is known, via the triangle inequality, that if we have an alpha-approximation for the discrete version, then we also have a beta*alpha-approximation for the continuous version, where beta depends on the problem; this beta is 2 for k-median and 4 for k-means. I will talk about whether this beta gap is "tight", i.e. can we do better for the continuous version than simply reducing to the discrete version and suffering a beta-factor blowup?

I will present positive results for k-means and a few related problems; the question is still open for k-median. The results are via a new linear program for these problems, and the use of the round-or-cut method via this linear program. This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.