<div dir="ltr"><div dir="ltr"><span class="gmail-m_5674691808897415648gmail-im"><div><div class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gE gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-iv gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gt" style="padding:10px 0px 3px"><p class="MsoNormal" style="color:rgb(80,0,80);margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>When:    </b>  Monday, October 1st at 11:00 am</font></p><p class="MsoNormal" style="color:rgb(80,0,80);margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="color:rgb(80,0,80);margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>Where:     </b>TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="color:rgb(80,0,80);margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif" style="color:rgb(80,0,80)"><b>Who:        </b></font><font color="#500050" face="arial, helvetica, sans-serif">Anand Louis, Indian Institute of Science</font></p><font face="arial, helvetica, sans-serif" style="color:rgb(80,0,80)"><br></font></div></div><div style="color:rgb(80,0,80)"><font face="arial, helvetica, sans-serif"><br></font></div></span><div><font face="arial, helvetica, sans-serif"><b>Title:</b>        On the Complexity of Clustering Problems</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b style="">Abstract:</b>  Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world data sets that allow efficient clustering has lead to the notion of the perturbation resilience. In the first part of the talk, I'll describe an algorithm to recover the optimal k-means clustering in perturbation resilient instances. </font></div><div><font face="arial, helvetica, sans-serif">In some cases, clustering with the k-means objective may result in a few clusters of very large cost and many clusters of small cost. This can be undesirable when we have a budget constraint on the cost of each cluster. Motivated by this, we study the "min-max k-means" clustering objective. In the second part of the talk, I'll show approximation algorithms for the min-max k-means problem.</font></div><div><font face="arial, helvetica, sans-serif"> </font></div><div><font face="arial, helvetica, sans-serif">Based on joint works with Amit Deshpande and Apoorv Vikram Singh.    <br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail-m_5674691808897415648gmail-adL"><span class="gmail-m_5674691808897415648gmail-im" style="color:rgb(80,0,80)"><font face="arial, helvetica, sans-serif"><div><div><b>Host: </b><a href="mailto:madhurt@ttic.edu">Madhur Tulsiani</a><br></div></div><div><br></div><div style=""><font style=""><span style="font-kerning:none">For more information on the <span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-il">colloquium</span></span></span></span></span></span></span> series or to subscribe to the mailing list,please </span>see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/<span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5674691808897415648gmail-m_-8045269396188967291m_8609159779071745624gmail-m_6134020100149053573gmail-il">colloquium</span></span></span></span></span></span>.php</a></font> <br></div></font></span></div><div dir="ltr"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr"><br></div><br class="gmail-Apple-interchange-newline"><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>