[Theory] NOW: 5/12 Talks at TTIC: Ankita Sarkar, Dartmouth University
Mary Marre
mmarre at ttic.edu
Fri May 12 10:32:22 CDT 2023
*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>*
On Fri, May 12, 2023 at 9:53 AM Mary Marre <mmarre at ttic.edu> wrote:
> *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>*
>
>
> On Thu, May 11, 2023 at 4:49 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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>*
>>
>>
>> On Fri, May 5, 2023 at 6:46 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20230512/a4f183c6/attachment-0001.html>
More information about the Theory
mailing list