<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)"> Friday, May 12</font><span class="gmail_default" style="color:rgb(0,0,0)">, 2023</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> <u style="background-color:rgb(255,255,0)">10:30 am</u></b><b><u><font color="#000000" style="background-color:rgb(255,255,0)"> CT</font></u><font color="#000000"> </font></b></font></font><br></font></div><div class="gmail_default"><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050">Where: </font></b><font color="#000000" style="font-family:arial,sans-serif">Talk will be given </font><font color="#000000" style="font-family:arial,sans-serif;font-weight:bold"><u>live, in-person</u></font><font style="font-family:arial,sans-serif;font-weight:bold"> </font><span style="font-family:arial,sans-serif">at</span><br></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> <i>via</i> Panopto </span>(<b><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9630c1be-fcd8-40fa-8911-aff9017f59a0" target="_blank">livestream</a></b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">)</span><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></span></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font>Ankita Sarkar, Dartmouth University<font color="#500050" style="font-family:arial,sans-serif"> </font><font color="#000000" style="font-family:arial,sans-serif"><font color="#500050"> </font></font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;color:rgb(80,0,80);text-align:center;line-height:15.6933px"><hr size="2" width="100%" align="center"></div><div><div dir="auto"><span id="m_1845852486723440935m_814812592570401779m_4313704277049077968m_-1641908334886248043gmail-docs-internal-guid-55a9450d-7fff-680a-e965-fd651d85f491"><font face="arial, sans-serif"><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Title:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-weight:normal">Approximation Algorithms for Continuous Clustering and Facility Location Problems</span></font></h3><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Abstract:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><font style="font-weight:normal">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.</font></font></h3><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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?</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.</span></p><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:4pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Bio:<span style="font-weight:normal"> </span></span><font style="font-weight:normal">Ankita Sarkar is a Ph.D. student in Theoretical Computer Science at Dartmouth Co</font><span style="font-weight:normal">llege, 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.</span></font></h3></font></span><br></div></div><div><div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif"><br></b></div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif">Host: </b><a href="mailto:vakilian@ttic.edu" target="_blank" style="font-family:arial,sans-serif"><b>Ali Vakilian</b></a></div></div></div><div><br style="color:rgb(80,0,80)"></div></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, May 12, 2023 at 9:53 AM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)"> Friday, May 12</font><span class="gmail_default" style="color:rgb(0,0,0)">, 2023</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> <u style="background-color:rgb(255,255,0)">10:30 am</u></b><b><u><font color="#000000" style="background-color:rgb(255,255,0)"> CT</font></u><font color="#000000"> </font></b></font></font><br></font></div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050">Where: </font></b><font color="#000000" style="font-family:arial,sans-serif">Talk will be given </font><font color="#000000" style="font-family:arial,sans-serif;font-weight:bold"><u>live, in-person</u></font><font style="font-family:arial,sans-serif;font-weight:bold"> </font><span style="font-family:arial,sans-serif">at</span><br></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> <i>via</i> Panopto </span>(<b><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9630c1be-fcd8-40fa-8911-aff9017f59a0" target="_blank">livestream</a></b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">)</span><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></span></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font>Ankita Sarkar, Dartmouth University<font color="#500050" style="font-family:arial,sans-serif"> </font><font color="#000000" style="font-family:arial,sans-serif"><font color="#500050"> </font></font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;color:rgb(80,0,80);text-align:center;line-height:15.6933px"><hr size="2" width="100%" align="center"></div><div><div dir="auto"><span id="m_1845852486723440935m_814812592570401779m_4313704277049077968m_-1641908334886248043gmail-docs-internal-guid-55a9450d-7fff-680a-e965-fd651d85f491"><font face="arial, sans-serif"><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Title:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-weight:normal">Approximation Algorithms for Continuous Clustering and Facility Location Problems</span></font></h3><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Abstract:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><font style="font-weight:normal">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.</font></font></h3><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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?</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.</span></p><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:4pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Bio:<span style="font-weight:normal"> </span></span><font style="font-weight:normal">Ankita Sarkar is a Ph.D. student in Theoretical Computer Science at Dartmouth Co</font><span style="font-weight:normal">llege, 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.</span></font></h3></font></span><br></div></div><div><div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif"><br></b></div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif">Host: </b><a href="mailto:vakilian@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Ali Vakilian</b></a></div></div></div><div><br></div><div><br></div><div><br></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 11, 2023 at 4:49 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)"> Friday, May 12</font><span class="gmail_default" style="color:rgb(0,0,0)">, 2023</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> <u style="background-color:rgb(255,255,0)">10:30 am</u></b><b><u><font color="#000000" style="background-color:rgb(255,255,0)"> CT</font></u><font color="#000000"> </font></b></font></font><br></font></div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050">Where: </font></b><font color="#000000" style="font-family:arial,sans-serif">Talk will be given </font><font color="#000000" style="font-family:arial,sans-serif;font-weight:bold"><u>live, in-person</u></font><font style="font-family:arial,sans-serif;font-weight:bold"> </font><span style="font-family:arial,sans-serif">at</span><br></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> <i>via</i> Panopto </span>(<b><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9630c1be-fcd8-40fa-8911-aff9017f59a0" target="_blank">livestream</a></b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">)</span><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></span></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font><span>Ankita</span> Sarkar, Dartmouth University<font color="#500050" style="font-family:arial,sans-serif"> </font><font color="#000000" style="font-family:arial,sans-serif"><font color="#500050"> </font></font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;color:rgb(80,0,80);text-align:center;line-height:15.6933px"><hr size="2" width="100%" align="center"></div><div><div dir="auto"><span id="m_1845852486723440935m_814812592570401779m_4313704277049077968m_-1641908334886248043gmail-docs-internal-guid-55a9450d-7fff-680a-e965-fd651d85f491"><font face="arial, sans-serif"><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Title:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-weight:normal">Approximation Algorithms for Continuous Clustering and Facility Location Problems</span></font></h3><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Abstract:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><font style="font-weight:normal">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.</font></font></h3><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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?</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.</span></p><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:4pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Bio:<span style="font-weight:normal"> </span></span><font style="font-weight:normal"><span>Ankita</span> Sarkar is a Ph.D. student in Theoretical Computer Science at Dartmouth Co</font><span style="font-weight:normal">llege, 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, <span>Ankita</span> studied mathematics and computer science at Chennai Mathematical Institute, India.</span></font></h3></font></span><br></div></div><div><div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif"><br></b></div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif">Host: </b><a href="mailto:vakilian@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Ali Vakilian</b></a></div></div></div><div><br></div><div><br></div><div><br></div><div><br></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, May 5, 2023 at 6:46 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div style="font-size:small"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)"> Friday, May 12</font><span class="gmail_default" style="color:rgb(0,0,0)">, 2023</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> <u style="background-color:rgb(255,255,0)">10:30 am</u></b><b><u><font color="#000000" style="background-color:rgb(255,255,0)"> CT</font></u><font color="#000000"> </font></b></font></font><br></font></div><div><p style="font-size:small;color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050"><br></font></b></p><p style="font-size:small;color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b style="font-family:arial,sans-serif"><font color="#500050">Where: </font></b><font color="#000000" style="font-family:arial,sans-serif">Talk will be given </font><font color="#000000" style="font-family:arial,sans-serif;font-weight:bold"><u>live, in-person</u></font><font style="font-family:arial,sans-serif;font-weight:bold"> </font><span style="font-family:arial,sans-serif">at</span><br></p><p class="MsoNormal" style="font-size:small;margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="font-size:small;margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="font-size:small;margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> <i>via</i> Panopto </span>(<b><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9630c1be-fcd8-40fa-8911-aff9017f59a0" target="_blank">livestream</a></b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">)</span><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></span></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font>Ankita Sarkar, Dartmouth University<font color="#500050" style="font-family:arial,sans-serif"> </font><font color="#000000" style="font-family:arial,sans-serif"><font color="#500050"> </font></font></p><div class="MsoNormal" align="center" style="font-size:small;margin:0in 0in 8pt;color:rgb(80,0,80);text-align:center;line-height:15.6933px"><hr size="2" width="100%" align="center"></div><div><div dir="auto"><span id="m_1845852486723440935m_814812592570401779m_4313704277049077968m_-1641908334886248043gmail-docs-internal-guid-55a9450d-7fff-680a-e965-fd651d85f491"><font face="arial, sans-serif"><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Title:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-weight:normal">Approximation Algorithms for Continuous Clustering and Facility Location Problems</span></font></h3><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:10pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Abstract:</span><span style="color:rgb(67,67,67);background-color:transparent;font-weight:400;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"> </span><font style="font-weight:normal">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.</font></font></h3><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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?</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">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.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">This is joint work with Deeparnab Chakrabarty and Maryam Negahbani, which appeared in ESA 2022.</span></p><h3 dir="ltr" style="line-height:1.38;margin-top:16pt;margin-bottom:4pt"><font size="2"><span style="color:rgb(67,67,67);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline;white-space:pre-wrap">Bio:<span style="font-weight:normal"> </span></span><font style="font-weight:normal">Ankita Sarkar is a Ph.D. student in Theoretical Computer Science at Dartmouth Co</font><span style="font-weight:normal">llege, 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.</span></font></h3></font></span><br></div></div><div style="font-size:small"><div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif"><br></b></div><div><b style="color:rgb(0,0,0);font-family:arial,sans-serif">Host: </b><a href="mailto:vakilian@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Ali Vakilian</b></a></div></div></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>