[Theory] 5/12 Talks at TTIC: Ankita Sarkar, Dartmouth University

[Mary Marre]

*When:*        Friday, May 12, 2023 at* 10:30 am** CT   *


*Where:       *Talk will be given *live, in-person* at

                   TTIC, 6045 S. Kenwood Avenue

                   5th Floor, Room 530


*Virtually:*  *via* Panopto (*livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9630c1be-fcd8-40fa-8911-aff9017f59a0>*
)


*Who:          *Ankita Sarkar, Dartmouth University
------------------------------
Title: Approximation Algorithms for Continuous Clustering and Facility
Location ProblemsAbstract: 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.

*Host: **Ali Vakilian* <vakilian at ttic.edu>



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230505/298de8ad/attachment-0001.html>